有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。

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

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

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

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

基于链码和特征形的多边形内外点判断算法

通过对多边形各个顶点与待测点相对位置进行判别,给出了多边形的垂直(水平)链码序列生成方法.该方法根据多边形的链码将原多边形中对判别无关的冗余边或冗余点删除,形成多边形的特征形;待测点在特征形与原多边形内外位置关系上具有一致性,从而大大简化了运算.同时给出了一种点在多边形内外点判断算法,把点在原多边形内外的判断转化为点与其特征形的位置判断,特征形的提取过程是一个线性扫描及条件判断过程,可以避免大量的叉积运算,从而有效地提高了多边形内外点判断算法的效率.程序验证表明:文中算法易于实现,具有运行速度快、稳定性高等优点.

点在多边形内测试的新算法

判断点在多边形内是诸多领域的一个基本问题。分析了解决这一问题的一些传统算法,改进了射线交叉法。避免了射线与多边形的一条边重合、射线经过多边形顶点这两种临界情况的处理和求交点运算。算法的时间复杂度为4n次减法,3n次乘法,6n次比较(n为多边形顶点数)。程序简单易行,计算量较小。

QT库中点与多边形位置判别算法Bug及解决方法

QT算法库为多边形QPolygon/QPolygonF提供containsPoint函数以判断点与多边形的位置关系。该函数在绝大多数情况下判别准确无误,但当点位于多边形边界上的特殊位置时,会出现判别错误。通过对QT算法库源码分析,发现原算法存在漏洞。在原算法基础上对Bug进行了修复,并可进一步提高算法效率。

一般平面区域内外点判别的算法

对一般平面区域内外点的判别提出了一套完备的算法。该算法已经成功地应用于级进模CAD/CAM系统软件设计,经受了实践的检验。实践表明算法稳定可靠。