Pythonで凹多角形かどうかを判定するプログラムの作り方

Pythonで凹多角形を判定する方法

多角形の外周上の頂点が時計回りの順序で与えられているとします。このとき、これらの頂点が凸多角形を形成しているかどうかを判定する必要があります。多角形の内角のうち一つでも180°より大きい角度が存在する場合、その多角形は凹多角形であると言えます。

次の図を見ると分かるように、連続する3つの頂点に着目して内角を確認すると、CDEの部分だけが180°を超えています。

そのため、入力が points = [(3,4), (4,7),(7,8),(8,4),(12,3),(10,1),(5,2)] のような場合、出力は True となります。

解決のための手順

この問題を解くには、以下の手順に従います。

• n := 頂点の総数
• i を 0 から頂点の数まで繰り返す
  • p1 := i > 1 の場合は points[i-2]、それ以外の場合は points[n-2]
  • p2 := i > 0 の場合は points[i-1]、それ以外の場合は points[n-1]
  • p3 := points[i]
  • 3点 (p1, p2, p3) がなす角度が 180° より大きい場合、True を返す
• ループが完了しても凹んだ箇所が見つからなければ False を返す

実装例

理解を深めるために、以下のPython実装を見てみましょう。math.atan2 を使うことで、2つのベクトルがなす角度を正確に求めることができます。

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