|
※この記事は凸包や線分アレンジメントなどの概念を理解し簡単な幾何の問題を解ける競技プログラマを対象としています。
代表的な幾何の問題として平面上の点の凸包を求めることを考えます。
凸包のアルゴリズムは色々と知られていますが、ここでは以下の単純なアルゴリズムを用いることにします。
２点を通る直線について全ての点が同じ側に存在しかつその時に限り、この２点を結ぶ線分は凸包の辺となる。
ただし、直線上の点についてはどちらの側にも属すると考える。
このアルゴリズムは以下の図のように３点が直線上にあるときに同じ辺を複数回数え上げてしまうという欠点があります。
TODO ３点が直線上にある時の図
このように幾何的に特殊な状態となっているコーナーケースのことを縮退と呼びます。
縮退を個別に処理するのは煩雑でバグの原因となりやすいです。
そこで、記号摂動法を用いて縮退そのものを解消してしまいます。
記号摂動法とは各点を微小距離移動することで縮退してない状態にすることです。
先ほどの例を摂動させてみると以下のようになります。
TODO 摂動後の図
凸包は左図でACD、右図でABCDとなります。
このようにして縮退を気にすること無く問題を解くことができるようになりました。
TODO
TODO
TODO
TODO
TODO
TODO
「コンピュータ・ジオメトリ 計算幾何学：アルゴリズムと応用」M.ドバーグ・M.ファン.クリベルド・M.オーバマーズ・O.シュワルツコップ共著 浅野哲夫訳 近代科学社
