Pythonで点が凸包を形成しているかどうかを判定する方法

多角形の外周にある頂点が時計回りの順序で与えられているとします。このとき、これらの点が凸包（コンベックスハル）を形成しているかどうかを判定する必要があります。

上の図からも分かるように、凸多角形では連続する3つの頂点からなる内角がすべて180°以下になります。つまり、すべての角度が180°以下であれば、その多角形は凸包であると判断できます。

例えば、入力が points = [(3,4), (4,7), (7,8), (11,6), (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]
  • (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

このプログラムでは、get_angle 関数が math.atan2 を利用して3点間の角度を計算しています。計算結果が負の値になった場合は360を加算することで正の角度に補正しています。続いて solve 関数が、隣接する3点ずつの角度を順番にチェックし、一つでも180°を超える箇所があれば False を返します。すべての角度が180°以下であれば、与えられた点列は凸包を形成していることになります。