百度站长seo,如何自己网站接装修生意做,多语言企业网站源码,哈尔滨做网站企业参考#xff1a;https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html
在GIS#xff08;地理信息管理系统#xff09;中#xff0c;判断一个坐标是否在多边形内部是个经常要遇到的问题。乍听起来还挺复杂。根据W. Randolph Franklin 提出的PNPoly算法#xff0c;…参考https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.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;
}ArgumentMeaningnvertNumber of vertices in the polygon. Whether to repeat the first vertex at the end is discussed below.vertx, vertyArrays containing the x- and y-coordinates of the polygon’s vertices.testx, testyX- and y-coordinate of the test point.
额代码就这么简单但到底啥意思呢
首先参数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两点间的斜率公式要用到一点初中解析几何和不等式的知识范畴对广大码农来说小菜一碟。
然后每次这两个条件同时满足的时候我们把返回的布尔量取反。
可这到底是啥意思啊
这个表达式的意思是说随便画个多边形随便定一个点然后通过这个点水平划一条线先数数看这条横线和多边形的边相交几次或者说先排除那些不相交的边第一个判断条件然后再数这条横线穿越多边形的次数是否为奇数如果是奇数那么该点在多边形内如果是偶数则在多边形外。详细的数学证明这里就不做了不过读者可以自行画多边形进行验证。
判断一个点是否在多边形内部 - 射线法思路 比如说我就随便涂了一个多边形和一个点现在我要给出一种通用的方法来判断这个点是不是在多边形内部别告诉我用肉眼观察……。 首先想到的一个解法是从这个点做一条射线计算它跟多边形边界的交点个数如果交点个数为奇数那么点在多边形内部否则点在多边形外。 这个结论很简单那它是怎么来的下面就简单讲解一下。
首先对于平面内任意闭合曲线我们都可以直观地认为曲线把平面分割成了内、外两部分其中“内”就是我们所谓的多边形区域。 基于这一认识对于平面内任意一条直线我们可以得出下面这些结论
直线穿越多边形边界时有且只有两种情况进入多边形或穿出多边形。 在不考虑非欧空间的情况下直线不可能从内部再次进入多边形或从外部再次穿出多边形即连续两次穿越边界的情况必然成对。 直线可以无限延伸而闭合曲线包围的区域是有限的因此最后一次穿越多边形边界一定是穿出多边形到达外部。
现在回到我们最初的题目。假如我们从一个给定的点做射线还可以得出下面两条结论
如果点在多边形内部射线第一次穿越边界一定是穿出多边形。 如果点在多边形外部射线第一次穿越边界一定是进入多边形。
把上面这些结论综合起来我们可以归纳出
当射线穿越多边形边界的次数为偶数时所有第偶数次包括最后一次穿越都是穿出因此所有第奇数次包括第一次穿越为穿入由此可推断点在多边形外部。
当射线穿越多边形边界的次数为奇数时所有第奇数次包括第一次和最后一次穿越都是穿出由此可推断点在多边形内部。 到这里我们已经了解了这个解法的思路大家可以试着自己写一个实现出来。
不知道大家思考得怎么样有没有遇到一些不好处理的特殊情况。今天就来讲讲射线法在实际应用中的一些问题和解决方案。
1点在多边形的边上
前面我们讲到射线法的主要思路就是计算射线穿越多边形边界的次数。那么对于点在多边形的边上这种特殊情况射线出发的这一次是否应该算作穿越呢 看了上面的图就会发现不管算不算穿越都会陷入两难的境地——同样落在多边形边上的点可能会得到相反的结果。这显然是不正确的因此对这种特殊情况需要特殊处理。
2点和多边形的顶点重合 这其实是第一种情况的一个特例。
3射线经过多边形顶点
射线刚好经过多边形顶点的时候应该算一次还是两次穿越这种情况比前两种复杂也是实现中的难点后面会讲解它的解决方案。 4射线刚好经过多边形的一条边
这是上一种情况的特例也就是说射线连续经过了多边形的两个相邻顶点。 解决方案
1判断点是否在线上的方法有很多比较简单直接的就是计算点与两个多边形顶点的连线斜率是否相等中学数学都学过。
2点和多边形顶点重合的情况更简单直接比较点的坐标就行了。
3顶点穿越看似棘手其实我们换一个角度思路会大不相同。先来回答一个问题射线穿越一条线段需要什么前提条件没错就是线段两个端点分别在射线两侧。只要想通这一点顶点穿越就迎刃而解了。这样一来我们只需要规定被射线穿越的点都算作其中一侧。 如上图假如我们规定射线经过的点都属于射线以上的一侧显然点D和发生顶点穿越的点C都位于射线Y的同一侧所以射线Y其实并没有穿越CD这条边。而点C和点B则分别位于射线Y的两侧所以射线Y和BC发生了穿越由此我们可以断定点Y在多边形内。同理射线X分别与AD和CD都发生了穿越因此点X在多边形外而射线Z没有和多边形发生穿越点Z位于多边形外。
解决了第三点这一点就毫无难度了。根据上面的假设射线连续经过的两个顶点显然都位于射线以上的一侧因此这种情况看作没有发生穿越就可以了。由于第三点的解决方案实际上已经覆盖到这种特例因此不需要再做特别的处理。
