图像处理

如何判别点在多边形内

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

封面图片 Dan Asaki

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

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

交点奇数，在内部

交点为偶数，在多边形外

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

点在多边形的一条边上，却是偶数个交点。

点在多边形的一个顶点上，如何计算交点个数？

多边形非凸，且有可能合并其它特殊情况。

设计的射线很不巧与多边形的一条边重叠。

所以，从方法上看这本是一个简单的交点个数统计问题，但是在实现时考验的是对各种特殊情况判别的完备性问题。一个 point_in_polygon 函数，测试用例我就写了15个。

Robins-MacBook:point_in_polygon yinguobing$ pytest
===================== test session starts =====================
platform darwin -- Python 3.9.10, pytest-7.1.2, pluggy-1.0.0
rootdir: /Users/Robin/Developer/point_in_polygon
collected 15 items                                                                                          

test_polygon.py ...............                                                                       [100%]

====================== 15 passed in 0.03s =====================

示例代码我放在GitHub上了，地址如下：