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

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

如何理解呢？

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

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

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

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

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

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

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

针对特殊情况3，可以通过设定这样的规则：若点的射线与多边形相交于多边形的顶点上，若该顶点为该边上纵坐标较大的点，则认为穿越一次。

如下图所示，

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

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

Matlab代码如下。

如果你有所收获，欢迎用微信扫一扫进行打赏，赏金随意。