在 Python 中检查给定点是否在给定多边形内部或边界上的程序

假设我们有一些笛卡尔坐标的点的列表 [(x1, y1), (x2, y2), …, (xn, yn)]，表示一个多边形，还有两个值 x 和 y，我们需要检查 (x, y) 是在这个多边形内部还是在边界上。

因此，如果输入为 points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt = (3, 1)

那么输出将为 True

为了解决这个问题，我们将进行以下步骤 −

• ans := False
• for i in range 0 to size of polygon – 1, do
  • (x0, y0) := polygon[i]
  • (x1, y1) := polygon[(i + 1) mod size of polygon]
  • if pt[1] 不在 y0、y1 的最小值和最大值范围之内，则
    • 进行下一次迭代
  • 如果 pt[0] < x0 和 x1 的最小值，则
    • 进行下一次迭代
  • cur_x := x0 if x0 is same as x1 otherwise x0 + (pt[1] – y0) *(x1 – x0) /(y1 – y0)
  • ans := ans XOR (当 pt[0] > cur_x 为 true 时，则为 1，否则为 0)
• return ans

我们来看一下以下实现，以便更好地理解 −

更多Python相关文章，请阅读：Python 教程

示例

class Solution:
   def solve(self, polygon, pt):
      ans = False
      for i in range(len(polygon)):
         x0, y0 = polygon[i]
         x1, y1 = polygon[(i + 1) % len(polygon)]
         if not min(y0, y1) < pt[1] <= max(y0, y1):
            continue
         if pt[0] < min(x0, x1):
            continue
         cur_x = x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
         ans ^= pt[0] > cur_x
      return ans

ob = Solution()
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
print(ob.solve(points, pt))

输入

[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)

输出

True