ポイントをチェックするプログラムがPythonで凸包を形成しているかどうか

ポリゴンの外側の点が時計回りにあるとします。これらの点が凸包を形成しているかどうかを確認する必要があります。

この図から、3つの連続するポイントごとに内角が180°以下であることが明らかです。したがって、すべての角度が180°以下の場合、ポリゴンは凸包になります。

したがって、入力がpoints =[（3,4）、（4,7）、（7,8）、（11,6）、（12,3）、（10,1）、（5,2 ）]の場合、出力はTrueになります。

これを解決するには、次の手順に従います-

• n：=ポイントのサイズ
• 0からポイントのサイズまでの範囲のiについては、
  • p1：=i> 1の場合はpoints[i-2]、それ以外の場合はpoints [n-2]
  • p2：=i> 0の場合はpoints[i-2]、それ以外の場合はpoints [n-1]
  • p3：=ポイント[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