今天讲如何判断一个点是否在一个多边形内部,先看demo:

判断点在多边形的内部还是外部 gif 判断点在多边形的内部还是外部

上图中横线和竖线的交点表示我们要测试的点,移动右边和下边的滚动条,调整横线和竖线的位置。要被测试的是一个中间带有空心的不规则形状,中间的空心属于外面,画虚线的部分才属于这个不规则形状的内部。

相交个数法

这种方法的主要思想就是判断这个点向右横切不规则图形的交点的个数:

如果向右横切交点的个数为奇数,那么表示在图形的内部;如果交点的个数为偶数,那么表示在图形的外部。

具体程序计算的时候,我们就遍历每一条边,计算那条边是否和点的右射线有交点,如果有,那我们就加一个,现在看看如何计算那个交点:

background Layer 1 p2 p1 p 1.p的纵坐标位于p1和p2之间,也就是p.y>p1.y&&p.y<=p2.y 2.p的横坐标不能超过p1,p2最大的,也就是p.x<Math.max(p1.x,p2.y) 3.计算出p的右射线和p1,p2的交点_p,且p的横坐标<_p的横坐标: _p 假设p1,p2的直线为y=k*x+b,其中k=(p2.y-p1.y)/(p2.x-p1.x) 因为p2在线上,那么p2.y=k*p2.x+b,那么b=p2.y-k*p2.x _p的纵坐标为p的纵坐标:p.y=k*x+p2.y-k*p2.x p.y-p2.y=k*(x-p2.x) (p.y-p2.y)/k+p2.x=x 最后得到p的横坐标:x=(p.y-p2.y)*(p2.x-p1.x)/(p2.y-p1.y)+p2.x

这里需要注意的是,边的数组一定要能形成一个封闭的多边形,也就是从起点出发最后一定要能够回到起点。并且这个计算方法适用于凸变形或者凹变形,或者中间带有空洞的不规则形状。

凸边同一方向

这种计算方式只适用于凸边形,这种的意思就是说在凸边形中如果顺时针遍历边,那么内部点在所有边的右边;如果逆时针遍历边,那么内部点在边的左侧。

background Layer 1 p0 p1 p 顺时针遍历边 如果p在内部,p点永远在p0p1的右侧 p1 p0 p 逆时针遍历边 如果p在内部,p点永远在p0p1的左侧

现在我们来看一个顺时针在右侧的情况,看看这两条线的斜率的关系:

background Layer 1 x y p0 p1 p k(p0p)>k(p0p1) (p.y-p0.y)/(p.x-p0.x)>(p1.y-p0.y)/(p1.x-p0.x)

需要注意的是我们这里的坐标和数学中的坐标是不太一样的,这里的y轴是向下的,那么p在p0p1的右侧的话,那么p0p的斜率肯定是大于p0p1的。

这样的话我们可以总结为,遍历所有的边,计算p0p和p0p1的斜率,如果在顺时针遍历的情况下,如果都是k(p0p)-k(p0p1)都是大于0的话,那么就是内部店;如果有一个小于0,那么就是外部点,如果有一个为0的,那么表示在线上。

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字