如何判别点在多边形内

我第一次遇到点在多边形内的判别问题是在研究生暑假。项目背景是在规划油田钻井设施位置时需要避开农田、村庄与水塘等特殊地块。没想到这么多年后在工作中又遇到了这个问题。这次干脆写一篇文章记录一下,方便以后查阅。

如何判别点在多边形内
封面图片 Dan Asaki

点在多边形内的判别是一个非常经典的问题。一个相对容易理解的方法为1962年由Shimrat M. 提出的射线法(Ray Casting algorithm) 。

Point in polygon - Wikipedia

该算法思路很简单:以待判别点为起点,向某个方向延长画一条射线,该射线与多边形的边可能会产生多个交点。若交点为奇数,则点在多边形内。若交点为偶数,则点在多边形外。

交点奇数,在内部
交点为偶数,在多边形外

算法本身没问题,但是在实际实现时却发现有众多特殊状况需要考虑。例如: