Python程式檢查點是否構成凸包

假設我們有按照順時針順序排列的多邊形的外點。我們需要檢查這些點是否構成凸包。

從該圖可以清楚地看出，對於每三個連續的點，內角都不超過180°。因此，如果所有角都不超過180°，則多邊形為凸包。

因此，如果輸入類似於 points = [(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)]，則輸出為 True。

為了解決這個問題，我們將遵循以下步驟：

  • n := points 的大小
  • 對於 i 從 0 到 points 的大小，執行以下操作
    • 當 i > 1 時，p1 := points[i-2]，否則 p1 := points[n-2]
    • 當 i > 0 時，p2 := points[i-2]，否則 p2 := points[n-1]
    • p3 := points[i]
    • 如果點 (p1, p2, p3) 之間的角度 > 180，則
      • 返回 False
  • 返回 True

示例

讓我們看看下面的實現以獲得更好的理解：

import math
def get_angle(a, b, c):
   angle = math.degrees(math.atan2(c[1]-b[1], c[0]-b[0]) - math.atan2(a[1]-b[1], a[0]-b[0]))
   return angle + 360 if angle < 0 else angle

def solve(points):
   n = len(points)
   for i in range(len(points)):
      p1 = points[i-2]
      p2 = points[i-1]
      p3 = points[i]
      if get_angle(p1, p2, p3) > 180:
         return False
   return True

points = [(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)]
print(solve(points))

輸入

[(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)]

輸出

True

更新於: 2021年10月12日

695 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告