2次元の凸包を求めるアルゴリズムと応用について

2次元の凸包(convex hull)を求めるアルゴリズムについてまとめました。また、凸包の応用先を列挙し、凸包を使って解ける競プロ問題を集めました。

この記事はデータ構造とアルゴリズム Advent Calendar 2018の17日目の記事です。前日はゆらふな(@yurahuna)さんのSentential Decision Diagramについてです。

凸包(convex hull)とは

凸包の定義

凸包(convex hull)とは，与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと.

与えられた点集合が凸集合であるとは、その集合に属する点の任意の対を結ぶ線分がその集合に含まれることを言うのであった。与えられた集合 X に対して、その凸包は以下の同値な条件：

X を含む（唯一の）最小の凸集合、

X を含む凸集合全ての交わり、

X に属する点から得られる凸結合全体の成す集合、

X に属する点を頂点とする単体全ての合併

の何れか一つ（従って全て）を満たす集合として定義される。

凸包 - Wikipedia

凸包の特徴

点集合Sに含まれる点のうち、ある軸で最小値・最大値を持つ点は凸包に含まれる
点集合Sについて、凸包上の点を内部に含む３点が存在しない
2次元の凸包は上部凸包(upper hull)と下部凸包(lower hull)に分けることができる

凸包を求めるアルゴリズム

ギフト包装法(1970)

ギフト包装法(Gift wrapping algorithm)やJarvisの行進法(Jarvis's march)。
半直線pqに対して、半直線qrのなす角が正かつ最小になるように全探索を行う。
n点からh点の凸包を構成する際の時間計算量はO(nh)になる。※hが小さいなら後述の分割統治より速い！

分割統治法で求める

凸包２つをマージする作業は上側接線と下側接線を求めて、内側を削除すれば良い。
n点からh点の凸包を構成する際の時間計算量はO(nlogn)になる。3次元への拡張が可能。

QuickHull(1977)

平均O(nlogn)、最悪O(n²)。4次元以上でも使えるのが強み。

グラハムスキャン(Graham's scan)(1972)

前処理としてソートを行うことで、ギフト包装法で次の点を決める際に貪欲に処理できるように工夫している。
n点からh点の凸包を構成する際の時間計算量はO(nlogn)になる。 2次元でしか使えない。

Monotone Chain(1979)

Andrew's algorithmとも。グラハムスキャンは偏角でソートしていたが、Monotone Chainは座標でソートする。定数倍の高速化になっている。
蟻本のP233にはグラハムスキャンとして紹介されている方法はこれ。
グラハムスキャン同様に2次元でしか使えない。

def det(p, q):
    return p[0]*q[1] - p[1]*q[0]


def sub(p, q):
    return (p[0]-q[0], p[1]-q[1])


def get_convex_hull(points):
    # どの3点も直線上に並んでいないと仮定する。
    n = len(points)
    points.sort()
    size_convex_hull = 0
    ch = []
    for i in range(n):
        while size_convex_hull > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    t = size_convex_hull
    for i in range(n-2, -1, -1):
        while size_convex_hull > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    return ch[:-1]

Chan's algorithm

O(n logh) - Chan's algorithm - Wikipedia - A Minimalist’s Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm

凸包を利用して解ける問題

凸包を利用して解ける問題の具体例

最遠点対(点集合の直径)を求める

最遠点対は凸包上の点である。 ※凸包の内部の点p,qが最遠点対だと仮定すると、半直線pqと交わる凸包上の辺abについてpa,pbの少なくともどちらかはpqより長くなることと矛盾する。

凸包上の点をいい感じに走査することで凸包の構築とは別にO(n)で最遠点対を見つけることができる。

他には

当たり判定のコストを下げる

TODO

コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用を読んで3次元の凸包について理解する

コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用

作者: M.ドバーグ,M.ファンクリベルド,M.オーバマーズ,O.チョン,Mark De Berg,Mark Overmars,Mark van Kreveld,Otfried Cheong,浅野哲夫
出版社/メーカー: 近代科学社
発売日: 2010/02/01
メディア: 単行本
購入: 4人クリック: 34回
この商品を含むブログ (5件) を見る

明日はjkr_2255(すんぶ)さんが「AST」についてです。よろしくお願いします。