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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告