判断一个坐标点是否在不规则多边形内部的算法

xiaoxiao2021-02-28  6

原文地址:http://www.cnblogs.com/armyfai/p/3529243.html

GIS(地理信息管理系统)中,判断一个坐标是否在多边形内部是个经常要遇到的问题。乍听起来还挺复杂。根据W. Randolph Franklin 提出的PNPoly算法,只需区区几行代码就解决了这个问题。

 

假设多边形的坐标存放在一个数组里,首先我们需要取得该数组在横坐标和纵坐标的最大值和最小值,根据这四个点算出一个四边型,首先判断目标坐标点是否在这个四边型之内,如果在这个四边型之外,那可以跳过后面较为复杂的计算,直接返回false

 

if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {

     // 这个测试都过不了。。。直接返回false

}

接下来是核心算法部分:

 

int pnpoly (int nvert, float *vertx, float *verty, float testx, float testy) {

    int i, j, c = 0;

    for (i = 0, j = nvert-1; i < nvert; j = i++) {

        if ( ( (verty[i]>testy) != (verty[j]>testy) ) &&

(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )

            c = !c;

    }

    return c;

}

 

额,代码就这么简单,但到底啥意思呢:

 

首先,参数nvert 代表多边形有几个点。浮点数testx, testy代表待测试点的横坐标和纵坐标,*vertx,*verty分别指向储存多边形横纵坐标数组的首地址。

我们注意到,每次计算都涉及到相邻的两个点和待测试点,然后考虑两个问题:

1. 被测试点的纵坐标testy是否在本次循环所测试的两个相邻点纵坐标范围之内?即

verty[i] <testy < verty[j]

或者

verty[j] <testy < verty[i]

2. 待测点test是否在i,j两点之间的连线之下?看不懂后半短if statement的朋友请自行在纸上写下i,j两点间的斜率公式,要用到一点初中解析几何和不等式的知识范畴,对广大码农来说小菜一碟。

然后每次这两个条件同时满足的时候我们把返回的布尔量取反。

可这到底是啥意思啊?

这个表达式的意思是说,随便画个多边形,随便定一个点,然后通过这个点水平划一条线,先数数看这条横线和多边形的边相交几次,(或者说先排除那些不相交的边,第一个判断条件),然后再数这条横线穿越多边形的次数是否为奇数,如果是奇数,那么该点在多边形内,如果是偶数,则在多边形外。详细的数学证明这里就不做了,不过读者可以自行画多边形进行验证。

转载请注明原文地址: https://www.6miu.com/read-200118.html

最新回复(0)