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

多角形の外側の点が時計回りにあるとします。これらの点が凸多角形を形成しているかどうかを確認する必要があります。ポリゴンの内角のいずれかが180°より大きい場合、ポリゴンは凹面であると言われます。

この図から、3つの連続するポイントごとに、CDEを除いて内角が180°以下であることが明らかです。

したがって、入力がpoints =[（3,4）、（4,7）、（7,8）、（8,4）、（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の場合、
    • Trueを返す
• Falseを返す

例

理解を深めるために、次の実装を見てみましょう-

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 True
   return False

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

入力

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

出力

True