09
08/2016
判断点是否在多边形区域里面
英语原文：https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
基本思想是，以该点向任意方向（这里是x轴正向）作射线，若与多边形的交点个数为偶数，则在多边形之外，否则在多边形之内。
这是作者给出的源代码：
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表示多边形点的个数，*vertx表示多边形点的x轴数组，*verty表示多边形点的y轴数组，testx和testy分别表示测试点的x、y轴。
对于i=0, j = nvert-1; i<nvert; j=i++的解释
这句话的意思是遍历一遍多边形的两个相邻点j, i。j在i之前。当i为0时，j为i的前一个点，即nvert-1。
对于(verty[i]>testy) != (verty[j]>testy)的解释
这句话表示点i和j必须在测试点y值的两侧。这里处理非常巧妙，而且防止了测试点、多边形相邻点在同一直线上，防止了后半部分条件中除数为0
对于testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]的解释
这句话利用了直线的两点式。
转载请注明：康瑞部落 » 判断点是否在多边形区域里面
0 条评论