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
  • 对于 i 从 0 到多边形大小 - 1，执行以下操作：
    • (x0, y0) := polygon[i]
    • (x1, y1) := polygon[(i + 1) mod 多边形大小]
    • 如果 pt[1] 不在 y0、y1 的最小值和最大值范围内，则：
      • 进入下一次迭代
    • 如果 pt[0] < x0 和 x1 的最小值，则：
      • 进入下一次迭代
    • cur_x := 如果 x0 等于 x1 则为 x0，否则为 x0 + (pt[1] - y0) *(x1 - x0) /(y1 - y0)
    • ans := ans XOR (如果 pt[0] > cur_x 为真，则为 1，否则为 0)
  • 返回 ans

让我们看看下面的实现来更好地理解：

示例

在线演示

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

更新于: 2020年12月3日

783 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告