基于斜率的多边形内外点快速判别算法

多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法。该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别。该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别。经测试,该算法快速有效。     

基于单调性与相关边的多边形内外点判断算法

为了充分挖掘多边形边的基本性质——单调性，基于检测点与多边形边之间的坐标关系，提出了相关边的概念及一种判断点在多边形内外的新算法。综合运用单调性与相关边技术，将点与我边形之间的位置关系转化为点与茯相关边之间的位置关系，从而尽可能地避免了叉积运算，且无需求交运算，从根本上提高了算法的效率，同时新算法还简单有效地解决了射线法中的临界位置问题。程序验证表明，新算法易于实现，适用于简单多边形，具有运行速度快、稳定性高等优点。     

基于拓扑映射的多边形顶点凸凹判别算法

通过拓扑映射，多边形顶点凸凹判别可以转化为映射点在射影直线上的位置关系问题。首先求得相邻边在两条射影直线上的映射点，基于一般映射点归纳得到顶点凸凹判别的4条规则，然后将两条射影直线上的映射点归结为一条射影直线，从而得到更有效的映射点求取方法，顶点凸凹判别规则统一为两条；进一步考虑非固有映射点的求取方法，提高了算法的稳定性，实验结果表明，该算法实现简单、速度快、稳定可靠。     

平面多边形内外点判定算法评估

以前的算法评估主要是基于“时间复杂度”和“空间复杂度”进行分析的,评估结果往往是一个含有多个参数的代数式。随着计算机软硬件技术的发展,算法评估指标也应该相应发展或创新。同时,随着评估技术的发展,算法评估应尽量给出一个明确的定量评估值。提出了包含便捷性、实用性、快速性、适用性、复杂性、正确性六个因素的一套算法评估指标体系,解释了每个指标的含义以及定量化表述方法。以平面多边形内外点的判定问题为背景,对于其中7个有代表性的算法,依据前面提及的评价指标体系进行了定量化的评估。数据实例显示,提出的方法是合理的、正确的、可行的。     

简单多边形凸凹性自识别算法

提出一种基于极值顶点构造凸多边形和矢量叉乘的自动识别简单多边形方向性，凸凹性的算法，该算法在稳定性方面采取了有效的措施，避免因极值顶点的奇异性而导致多边形方向性，凸凹性的错误识别，具有良好的可靠性和稳定性，算法原理直观简单，效率高，时间复杂度为O（n).     

点与简单多边形关系的新算法

提出一种检测点与多边形关系的新算法,通过扫描建立适合查找的多边形层次结构。检测时,运用二分查找,找到与检测点相关的边,通过该点与相关边的关系判断出点与多边形的关系。实验结果表明,该方法简单有效,有较高的检测速度。     

多边形内点的编码法测定算法

本文叙述了一种测定多边形内点的编码法算法原理。该算法基本避免了求交运算,从而大大减少了内点测定的计算量。     

平面多边形方向及内外点判断的新方法

提出了一种通过构造一个与平面多边形拓扑同构的、严格凸多边形判断方向的新方法,分析了退化情况并给出了处理方法,基于受约束的三角划分的思想,提出了一种新的判断点在多边形内的准则,并给出了算法,实际应用表明,这两个算法隐定,可靠,而且简单。     

基于单调链的判断点是否在多边形内的方法

提出了一种判断点是否在多边形内的新方法，该方法由两部分组成：(1)预处理，即先求出多边形的所有极点；(2)检测，即采用折半查找找到相关点和相关边，根据被检测线穿过的相关边数来判断检测点是否在多边形内。该方法解决了射线法无法解决的奇异情况，且在检测过程中不必处理多边形的所有边。实验结果证明，该方法简单、易实现、快速。     

一种剖分平面多边形的通用算法描述

提出了一种用梯形来剖分非单调平面多边形的通用算法，算法包括三部分：初始化，梯形化和优化（后处理），所处理的多边形可以包含孔，孔可以嵌套。本算法的时间复杂度是O(n^2log2n).     

一种剖分平面多边形的通用算法执行

对一种用梯形来剖分非单调平面多边形的通用算法，在AMD雷鸟750MHZ CPU计算机上进行了计算，结果表明，本算法可以有效、经济地处理大量复杂的多边形，经优化处理后，可减少约34%的梯形个数。     

一种判定点和多边形包含关系的有效方法

在分析现有点与多边形包含关系的判定方法的基础上,提出了将判断点绕多边形的一个适当顶点为中心逆时针旋转,根据判断点依次旋转到该顶点前后两边时两个旋转角的大小关系来判定点的位置的思想,并以此为基础提出了一种判定点与多边形的包含关系的有效方法。     

映射相关边概念的多边形内外点判别算法

提出映射相关边、密切边的概念,将点在多边形内外的判别转化为点与密切边关系的判别．通过X方向的一次映射快速求取判别点的相关边,对相关边的二次映射可得到判别点的密切边．证明了根据密切边的矢量方向就可以判别点在多边形内外．在运算效率上对射线法进行改进,当多边形的边数较多时,更能体现文中算法优越性．     

基于边方向角长度表示的多边形方向、凹凸性及点包含算法

提出矢量边方向角的长度表示概念,用于解决多边形方向识别、顶点凹凸性识别和点包含判断三个问题.给出了基于矢量边方向角长度概念描述多边形边方向角的单调连续函数,当方向角从0°增加到360°时,函数值从0增加到8,该函数可以准确地表达多边形中边矢量的方向角,也可以准确地表达待检测点与多边形顶点连线所形成矢量的方向角.建立了基于矢量边方向角长度概念的多边形相邻边左右侧走向关系判定规则.该规则可用于判定相邻边方向关系,实现多边形方向识别和顶点凹凸性识别;计算待检测点与多边形顶点连线之间所夹有向边方向角长度和,实现点包含判断.给出了三个问题的实现算法,该算法与目前最优算法复杂度相同,但计算量较最优算法少1次乘除类运算,同时保证了高可靠性、稳定性和执行效率.实现了三个问题解决方法在几何概念上的统一,而在其他同类算法中几何概念是相互独立的.     

Robust and Optimized Algorithms for the Point‐in‐Polygon Inclusion Test without Pre‐processing

In this work we present new point inclusion algorithms for non‐convex polygons. These algorithms do not perform any pre‐processing or any type of decomposition nor features classification, which makes them especially suitable for deformable or moving polygons. The algorithms are more accurate and robust than others in the sense that they consider the inclusion of the point in the vertices and edges of the polygon, and deal with the special cases correctly. In order to perform this inclusion test efficiently, they use the sign of the barycentric coordinates of the test point with regard to the triangles formed by the edges and an origin that depends on the test point. This set of triangles, which is a special simplicial covering of the polygon, is constructed after a transformation of the polygon that simplifies the calculations involved in the inclusion test. Then, an appropriate ordering of the rejection tests allows us to optimize this method. Our algorithms have been tested for robustness and compared with ray‐crossing methods, showing a significant improvement.