判断一点是否在多边形内部：射线法
2019-01-07 21:47阅读：
在几何学中，PIP（Point in Polygon）问题即判断一点在多边形的内部或外部。
射线法（Ray casting
algorithm）是一种判断点是否在多边形内部的一种简单方法。即从该点做一条射线，计算它跟多边形边界的交点个数，如果交点个数为奇数，那么点在多边形内部，否则点在多边形外部。
如何理解呢？
其实，对于平面内任意闭合曲线，曲线都把平面分割成了内、外两部分。对于平面内任意一条直线，在穿越多边形边界时，有且只有两种情况：进入多边形或穿出多边形。即：
- 如果点在多边形内部，射线第一次穿越边界一定是穿出多边形。
- 如果点在多边形外部，射线第一次穿越边界一定是
进入多边形。
由于直线可以无限延伸，而闭合曲线包围的区域是有限的，因此最后一次穿越多边形边界，一定是穿出多边形，到达外部。
由上可推断，从一点做一条射线，计算它跟多边形边界的交点个数，如果交点个数为奇数，那么点在多边形内部，否则点在多边形外部。
需要注意以下几种特殊情况：
- 点在多边形的顶点或边上
- 点在多边形边的延长线上
- 点的射线与多边形相交于多边形的顶点上
针对特殊情况1，只需判断点是否在多边形的边线上即可。
针对特殊情况3，可以通过设定这样的规则：
若点的射线与多边形相交于多边形的顶点上，若该顶点为该边上纵坐标较大的点，则认为穿越一次。
如下图所示，
- X点的射线经过D点，但D点纵坐标均大于A和C点，因此，穿越次数为2；
- Y点的射线经过C点，但C点纵坐标大于B点，但小于D点，因此，穿越次数为1；
- Z点的射线经过B点，但B点纵坐标均小于A和C点，因此，穿越次数为0；
针对特殊情况2的处理，在对特殊情况3的处理中已经有所包括，即穿越次数为0。
Matlab代码如下。
如果你有所收获，欢迎用微信扫一扫进行打赏，赏金随意。
