判断一个坐标点是否在不规则多边形内部
在 GIS（地理信息管理系统）中，判断一个坐标是否在多边形内部是个经常要遇到的问题。乍听起来还挺复杂。根据 W. Randolph Franklin 提出的 PNPoly 算法，只需区区几行代码就解决了这个问题。
在多边形的顶点中分别找出 X 坐标和 Y 坐标的最小/最大值。比如，你有点(9,1),(4,3),(2,7),(8,2),(3,6)所围成的多边形。那么 Xmin 为2，Xmax 为9，Ymin 为1，Ymax 为7。现在我们知道你的多边形中没有一个点的 X 坐标比2小或者比9大，也没有一个点的 Y 坐标比1小或者比7大。这样你就可以快速排除很多不在多边形中的点。
def point_in_polygon(x, y, verts):
"""
- PNPoly算法
- xyverts [(x1, y1), (x2, y2), (x3, y3), ...]
"""
try:
x, y = float(x), float(y)
except:
return False
vertx = [xyvert[0] for xyvert in verts]
verty = [xyvert[1] for xyvert in verts]
# N个点中，横坐标和纵坐标的最大值和最小值，判断目标坐标点是否在这个四边形之内
if not verts or not min(vertx) <= x <= max(vertx) or not min(verty) <= y <= max(verty):
return False
# 上一步通过后，核心算法部分
nvert = len(verts)
is_in = False
for i in range(nvert):
j = nvert - 1 if i == 0 else i - 1
if ((verty[i] > y) != (verty[j] > y)) and (
x < (vertx[j] - vertx[i]) * (y - verty[i]) / (verty[j] - verty[i]) + vertx[i]):
is_in = not is_in
return is_in
