Convex Hull (Ice Base) - 凸型ポリゴン

来週から、1ヶ月ほど海外に行くので、出発までになんとか全問クリアしたかったのだが、ちょっと厳しいかなぁ・・・。

どんな問題？

Convex Hull
http://www.checkio.org/mission/convex-hull/

与えられた点からなる凸型ポリゴンを取得せよ。
最も左側にある一番下の点を開始点として、ポリゴンの頂点を時計回りに求める。

引数は、点の座標が [x,y]形式のリストとして与えられる。点の数は1以上10未満。座標の値は 0＜x,y＜10 の範囲の整数値となる。
戻り値は、頂点のインデックスをリストとして返す。

例題：

checkio([[7, 6], [8, 4], [7, 2], [3, 2], [1, 6], [1, 8], [4, 9]]) == [4, 5, 6, 0, 1, 2, 3]
checkio([[3, 8], [1, 6], [6, 2], [7, 6], [5, 5], [8, 4], [6, 8]]) == [1, 0, 6, 3, 5, 2]

どうやって解く？

なんか公式がありそうだが、まずは何も見ずに解いてみよう。
Wikipediaに「輪ゴムを掛けたようなもの」という表現があったが、外側から囲むようなイメージで考えれば解けそうだ。

最初の点 P1 は、最も左側にある一番下の点となる。
P2 は、P1より右側にあるわけだから、P1の真下に仮のP0を作って、P0-P1-P2の角度が最大になる（つまり線分P0-P1と線分P1-P2の角度が最小になる）ような点 P2 を探せばいい。

最初の点 P1 と次の点 P2 が確定すれば、同じようにして、P1-P2-P3の角度が最大になる（つまり線分P1-P2と線分P2-P3の角度が最小になる）ような点 P3 を探せばいい。
P4以後はその繰り返し。

角度を求めるには、math.atan2を使えばいいようだ。

def get_angle(pt1, pt2):
    return atan2(pt2[1] - pt1[1], pt2[0] - pt1[0])

開始点から、他の点までの角度を計算し、角度の差が最小のものが次の点となる。
ただし、角度が同じ場合もあるので、そのときは、近い点を優先するようにした。
また、引数の点の数は1個以上なので、1個のときは[0]を返すようにしている。
あれこれ追加して、最終的にこうなった。

まとめ

from math import atan2, hypot, pi
 
def get_angle(pt1, pt2):
    # ベクトル(pt1→pt2)とX軸との角度
    return atan2(pt2[1] - pt1[1], pt2[0] - pt1[0])
 
def get_distance(pt1, pt2):
    # pt1とpt2の距離
    return hypot(pt2[0] - pt1[0], pt2[1] - pt1[0])
 
def checkio(data):
    if len(data) == 1:
        return [0]
    point = min([p for p in data if p[0] == min(data)[0]])  # 一番左の下が開始点
    angle = pi / 2  # 最初の角度は90度とする
    result = [data.index(point)]
    while True:
        # pointから他点への角度を計算
        pts_data = [(i, p, get_angle(point, p)) for i, p in enumerate(data) if p != point]
        # 同じ角度なら距離が近い方を優先するためソートしておく
        pts_data.sort(key=lambda d: get_distance(point, d[1]))
        # 前の角度との差が最小になる点が次の点
        index, point, angle = min(pts_data, key=lambda d: (angle - d[2]) % (pi * 2))
        # すでにresultに含まれている点ならポリゴン完成
        if index in result:
            return result
        result.append(index)

http://www.checkio.org/mission/convex-hull/publications/natsuki/python-3/first/

なんか、ごちゃごちゃしてて見づらくなってしまった。