判断点是否在多边形中的方式:
搜索网络资源,发现判断点是否在多边形内的方式一般是以点为射线端点,向另一无穷远处做射线,判断此条射线与多边形各条边的相交情况,如果相交次数为奇数,认为点在多边形内或在多边形上,否则,认为点在多边形外.如图
这个方法无非就是判断相交次数.
具体操作时,可以简化一下:
看上图,如果要判断p1x,p1y点是否在多边形内,只需要取能够与之相交的线段进行判断而已.我这里恒认为x轴为0,y轴与测试点相同的点为射线的另一段,那么,只有y值在测试点p1y上下的线段才是我们要测试的线段,比如上图中的x3,y3和x4,y4,那么有此条件,判断设想是否和x3y3x4y4相交无非就是判断p1.X > Max(x3.X,x4.X)而已,如果成立,则射线与x3y3x4y4线段相交,如果线段的两个端点的Y值均大于或均小于p1的Y值,则无判断的必要.因为它们不可能相交.
如果是p2xp2y的情况则需要做跨立判断,因为p2x介于x4x和x5x之间,p2y介于x4y和x5y之间.
假设,p2和x4x5相交,那么它们的交点tmpP的X必定小于p2X,tmpY必定等于p2Y,
我们做x4y4x5y5的直线方程:
ax + by + c = 0
a = y5-y4
b = x5-x4
c = (x5-x4)y4 –(y5-y4)x4
令y=p2Y;
那么x = (x5-x4)p2Y + ((x5-x4)y4 –(y5-y4)x4)/(y4-y5)
如果x < p2X,那么两线相交,否则两线不相交.
评论