判断点在多边形内部

《判断点在多边形内部》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、判断点在多边形内部0.前言最近不断遇到类似的几何位置问题，一直没有花时间去总结，本文总结了我常用点跟多边形的位置判断方法以及代码。希望能够对大家有所帮助。文中所指的多边形均为凸多边形，一些描述可能有误，欢迎指正。1.测试的多边形在开始之前，我们需要先构建好测试环境。我构建了一个比较特殊的多边形，如下。/

2、 

3、

4、_

5、从最上面的顶点顺时针坐标（屏幕坐标系）分别为：(40,10) (60,30)(60,50) (20,50) (20,30)2.射线判别法 根据对多边形的了解，我们可以得出如下结论：如果一个点在多边形内部，任意角度做射线肯定会与多边形要么有一个交点

6、，要么有与多边形边界线重叠。如果一个点在多边形外部，任意角度做射线要么与多边形有一个交点，要么有两个交点，要么没有交点，要么有与多边形边界线重叠。利用上面的结论，我们只要判断这个点与多边形的交点个数，就可以判断出点与多边形的位置关系了。首先罗列下注意事项:l 射线跟多边形的边界线重叠的情况l 区别内部点和外部点的射线在有一个交点时的情况对于第一个注意事项，可以将射线角度设为零度，这样子只需要判断两个相邻顶点的Y值是否相等即可。然后再判断这个点的X值方位。对于第二个注意事项，网上许多文章都说到做射线以后交点为奇数则表示在多边形内部，这是一个错误的观点，不仅对于

7、凹多边形不成立，对于凸多边形也不成立。例如：从外部点做射线刚好经过一顶点，这样子交点个数就为奇数，但是该点却不在多边形内部。至于要如何区分这两种情况呢，我能想到了一个不完美的方法，外部点的射线跟多边形有一个交点的时候，该交点肯定为顶点，如果该射线上移一位或者下移一位，要么变成有两个交点要么没有交点。当然为了安全起见，这里把射线尽量往相邻点中心移动。这样子就能够判断出是外部点的射线跟多边形有一个交点。不过这个方法并不完美，因为有了移位操作，可能会把内部点移动出外部。而且如果判断点在(60,30)位置，判断的时候先遇到(20,30)，然后移位操作，就判断就出错了

8、。为了解决这些问题，我在起初先扫描一次判断点是否在顶点上虽然影响了一点效率，而且当判定点距离多边形一个单位时，判断可能会有误。不过只要不是需要高精度的话，这个方法还是很有效的。代码如下：boolInsidePolygon1(POINTD*polygon,intN,POINTDpt){inti,j;boolinside,redo;redo=true;for(i=0;i

9、do){redo=false;inside=false;for(i=0,j=N-1;i

10、

11、(polygon[j].y

12、

13、pt.x<=polygon[j].x){double_x=(pt.y-polygon[i].y)*(polygon[j].x-polygon[i].x)/(polygon[j].y-polygon[i].y)+polygon[i].x;if(pt

14、.x<_x)//在线的左侧inside=!inside;elseif(pt.x==_x)//在线上{inside=true;break;}}}elseif(pt.y==polygon[i].y){if(pt.xpolygon[j].y?--pt.y:++pt.y;redo=true;break;}}elseif(polygon[i].y==polygon[j].y&&//在水平的边界线上pt.y==polygon[i].y&&((polygon[i].x

15、on[j].x)

16、

17、(polygon[j].x

18、constPOINTD&pt,constPOINTD