wordpress主题网站,高级软件开发培训,建站平台哪家好,河西网站建设优化seo在计算几何中#xff0c;判定点是否在多边形内#xff0c;是个非常有趣的问题。通常有两种方法#xff1a;
一、Crossing Number#xff08;交叉数#xff09;
它计算从点P开始的射线穿过多边形边界的次数。当“交叉数”是偶数时#xff0c;点在外面;当它是奇数时…在计算几何中判定点是否在多边形内是个非常有趣的问题。通常有两种方法
一、Crossing Number交叉数
它计算从点P开始的射线穿过多边形边界的次数。当“交叉数”是偶数时点在外面;当它是奇数时点在里面。这种方法有时被称为“奇-偶”检验。
如果一个多边形是不自交的称为“简单多边形”那么这两种方法对任意点都给出相同的结果。但对于非简单多边形这两种方法在某些情况下会给出不同的答案。如下图所示当一个多边形与自身重叠时对于重叠区域内的点如果使用交叉数判断它在外面而使用环绕数判断则在里面。 在上图中绿色区域中的点wn 2表示在多边形中重叠了2次。相比于Crossing numberwinding number给出了更内蕴性的答案。
尽管如此早些时候crossing number方法应用的更广泛因为最初计算几何专家们错误地认为crossing number比winding number计算起来更加高效。但事实并非如此两者的时间复杂度完全一样。Franklin在2000年给出一个计算winding number的非常快的实现。因此为了几何正确性和效率的原因在确定一个多边形中的一个点时wn算法应该总是首选的。
该方法计算从点P开始的射线穿过多边形边界的次数不管穿过的方向。如果这个数是偶数那么点在外面;否则当交叉数为奇数时点在多边形内。其正确性很容易理解因为每次射线穿过多边形边缘时它的内外奇偶性都会发生变化(因为边界总是分隔内外)。最终任何射线都在边界多边形之外结束。所以如果点在多边形内那么对边界的穿过次序一定是out…inout,因此交叉数一定是奇数同样地如果点在多边形外那么对边界的穿过次序一定是in out … in out,因此交叉数必是偶数。 在实现crossing number的算法时必须确保只计算改变奇偶性的交叉位置。特别是对于射线穿过顶点的情况需要适当的处理。下图列举了射线与多边形可能的相交情况 此外必须确定多边形边界上的点P是在内部还是外部。一般约定如果点在边的左侧那么认为点P在内部如果点在边的右侧那么认为点P在外部。如果两个不同的多边形共享一个共同的边界线段那么该线段上的一点将会在一个多边形或另一个多边形中而不是同时在两个多边形中。这避免了许多可能发生的问题特别是在计算机图形显示中。
一个简单的做法是选择一条x轴正方向的水平射线对于这样一条射线很容易计算多边形的边与它的交点。而且很容易确定交点是否存在。算法只需沿着多边形的每一条边依次计算交点当相交时cn增加1从而计算出最终的总交叉数。
此外相交测试必须遵循如下的规则处理一些特殊情况如上图
向上的边包含起点但不包含终点向下的边包含终点但不包含起点水平的边不包含起点和终点边与射线的交点必须严格在点P的右侧
按照上述规则处理特殊的相交情况就能得到正确的交叉数。其中规则4将导致在边界右侧的点在多边形外部在左侧的点将会被判定为在内部。
Crossing Number Pseudo-Code 对于n个点组成的多边形V{V[0], V[1], …,V[n]},其中V[n]V[0], 计算几何大牛Franklin给出了一个非常有名的实现
typedef struct {int x, y;} Point;cn_PnPoly( Point P, Point V[], int n )
{int cn 0; // the crossing number counter// loop through all edges of the polygonfor (each edge E[i]:V[i]V[i1] of the polygon) {if (E[i] crosses upward ala Rule #1|| E[i] crosses downward ala Rule #2) {if (P.x x_intersect of E[i] with yP.y) // Rule #4cn; // a valid crossing to the right of P.x}}return (cn1); // 0 if even (out), and 1 if odd (in)}注意对于满足规则1和2的向上和向下交叉的测试也排除了水平边缘(规则3)。总而言之很多工作是通过几个测试完成的这使得这个算法很优雅。
然而交叉数方法的有效性是基于“约当曲线定理”Jordan Curve Theorem该定理表明一条简单的闭合曲线将二维平面分成两个完全连通的分量:一个有界的“内”分量和一个无界的“外”分量。需要注意的是曲线必须是简单的(没有自身交叉)否则可能有两个以上的组成部分然后就不能保证跨越边界改变进出奇偶性。因此该方法不适用于自相交的多边形。
二、Winding Number环绕数
它计算多边形绕着点P旋转的次数。只有当“圈数”wn 0时点才在外面; 否则点在里面。
winding number方法能准确判定一个点是否在自交的封闭曲线内。该方法通过计算多边形有多少次环绕点P来实现。只有当多边形不环绕该点也就是环绕数wn 0时一个点才在外面。
不妨定义平面上的点P相对于任意连续封闭曲线的环绕数为{wn}(P,C)。对于一条水平向右的射线R我们每一条与R相交的边需要判断其终点在R上面还是下面。如果边从下往上穿过Rwn1否则wn-1。所有边遍历一遍最终得到总的f{wn}(P,C)如下图所示
此外我们没必要计算实际的交点只需要使用如下方法判断当前穿过的边的环绕数应该1还是-1
如下图所示如果一条边向上穿过射线R那么P点在边ViVi1的左侧而对于一条向下的边P点在边ViVi1的右侧。
通过以上分析容易给出如下的wn计算伪代码和cn的计算一样使用相同的边相交规则 typedef struct {int x, y;} Point;wn_PnPoly( Point P, Point V[], int n )
{int wn 0; // the winding number counter// loop through all edges of the polygonfor (each edge E[i]:V[i]V[i1] of the polygon) {if (E[i] crosses upward ala Rule #1) {if (P is strictly left of E[i]) // Rule #4wn; // a valid up intersect right of P.x}elseif (E[i] crosses downward ala Rule #2) {if (P is strictly right of E[i]) // Rule #4--wn; // a valid down intersect right of P.x}}return wn; // 0 P is outside the polygon}显然环绕数方法与交叉数方法有着相同的计算效率。但由于该方法更加具有普遍性因此在确定一个点是否在任意多边形内时推荐使用Winding Number方法。
通过一些技巧可以进一步提高wn算法的效率在下面给出的wn_PnPoly() 的实现中我们可以看到这一点。在该代码中所有完全在P以上或完全在P以下的边只经过两次不等式检验就被拒绝没有交点。然而在目前流行的cn算法的实现中需要3次不等式检验才能做到这一点。由于在实际应用中大多数边都会被拒绝因此进行比较的次数减少了大约33%(或更多)。在使用非常大的(1,000,000边)随机多边形(边长多边形直径的1/10)和1000个随机测试点(在多边形的边界内)进行运行时测试时测试结果表明wn算法的平均效率提高了20%。
