如何判别点在多边形内
我第一次遇到点在多边形内的判别问题是在研究生暑假。项目背景是在规划油田钻井设施位置时需要避开农田、村庄与水塘等特殊地块。没想到这么多年后在工作中又遇到了这个问题。这次干脆写一篇文章记录一下，方便以后查阅。
点在多边形内的判别是一个非常经典的问题。一个相对容易理解的方法为1962年由Shimrat M. 提出的射线法（Ray Casting algorithm） 。
Point in polygon - Wikipedia
Contributors to Wikimedia projects
该算法思路很简单：以待判别点为起点，向某个方向延长画一条射线，该射线与多边形的边可能会产生多个交点。若交点为奇数，则点在多边形内。若交点为偶数，则点在多边形外。
算法本身没问题，但是在实际实现时却发现有众多特殊状况需要考虑。例如：
