判断一点是否在多边形内部：射线法

PIP问题

在几何学中，PIP（Point in Polygon）问题：即判断一点在多边形的内部或外部的问题。

射线法（Ray casting algorithm）是一种判断点是否在多边形内部的一种简单方法。即从该点做一条射线，计算它跟多边形边界的交点个数，如果交点个数为奇数，那么点在多边形内部，否则点在多边形外部。

射线法

如何理解呢？

其实，对于平面内任意闭合曲线，曲线都把平面分割成了内、外两部分。对于平面内任意一条直线，在穿越多边形边界时，有且只有两种情况：进入多边形或穿出多边形。即：

• 如果点在多边形内部，射线第一次穿越边界一定是穿出多边形。
• 如果点在多边形外部，射线第一次穿越边界一定是进入多边形。

由于直线可以无限延伸，而闭合曲线包围的区域是有限的，因此最后一次穿越多边形边界，一定是穿出多边形，到达外部。

由上可推断，从一点做一条射线，计算它跟多边形边界的交点个数，如果交点个数为奇数，那么点在多边形内部；如果交点个数为偶数，则点在多边形外部。

需要注意以下几种特殊情况：

1. 点在多边形的顶点或边上
2. 点在多边形边的延长线上
3. 点的射线与多边形相交于多边形的顶点上

特殊情况1

特殊情况3

特殊情况2

针对特殊情况1，只需判断点是否在多边形的边线上即可。

针对特殊情况3，可以通过设定这样的规则：

若点的射线与多边形相交于多边形的顶点上，若该顶点为该边上纵坐标较大的点，则认为穿越一次。

如下图所示，

X点的射线经过D点，但D点纵坐标均大于A和C点，因此，穿越次数为2；

Y点的射线经过C点，但C点纵坐标大于B点，但小于D点，因此，穿越次数为1；

Z点的射线经过B点，但B点纵坐标均小于A和C点，因此，穿越次数为0；

特殊情况3的处理

针对特殊情况2的处理，在对特殊情况3的处理中已经有所包括，即穿越次数为0。

小提示：在依次判断点的射线与每条边的相交情况之前，可以先对多边形做一下坐标转换，方便计算，即将多边形转换到以判断点为原点的坐标系中。

Matlab代码如下。

主程序

判断点是否在多边形内部

判断点是否在线上

计算与x轴的交点横坐标

閱讀更多 算法集市 的文章

關鍵字: 多边形 个数 技术