在GIS（地理信息管理系统）中判斷一个坐标是否在点在多边形内内部是个经常要遇到的问题。乍听起来还挺复杂根据W。 Randolph Franklin 提出的PNPoly算法只需区区几行代码就解决了这个问題。
假设点在多边形内的坐标存放在一个数组里首先我们需要取得该数组在横坐标和纵坐标的最大值和最小值，根据这四个点算出一个㈣边型首先判断目标坐标点是否在这个四边型之内，如果在这个四边型之外那可以跳过后面较为复杂的计算，直接返回false
if (p。x maxX || py 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 testy) != (verty[j]>testy) ) &&
(testx c = !c;
 }
 return c;
}
额代码就这么简单，但到底啥意思呢：
首先参数nvert 代表点在多边形内有几个点。
 浮点数testx, testy代表待测试点的横坐标和纵坐标*vertx,*verty分别指向储存点在多边形内横纵坐标数组的首地址。
我们注意到每次计算都涉及到相邻的两个點和待测试点，然后考虑两个问题：
1
 被测试点的纵坐标testy是否在本次循环所测试的两个相邻点纵坐标范围之内？即
verty[i] 或者
verty[j] 2
 待测点test是否在i,j两點之间的连线之下？看不懂后半短if statement的朋友请自行在纸上写下i,j两点间的斜率公式要用到一点初中解析几何和不等式的知识范畴，对广大码農来说小菜一碟
然后每次这两个条件同时满足的时候我们把返回的布尔量取反。
可这到底是啥意思啊
这个表达式的意思是说，随便画個点在多边形内随便定一个点，然后通过这个点水平划一条线先数数看这条横线和点在多边形内的边相交几次，（或者说先排除那些鈈相交的边第一个判断条件），然后再数这条横线穿越点在多边形内的次数是否为奇数如果是奇数，那么该点在点在多边形内内如果是偶数，则在点在多边形内外
 详细的数学证明这里就不做了，不过读者可以自行画点在多边形内进行验证

以上内容为魔方格学习社区（）原创内容未经允许不得转载！