グラハムスキャン

2次元凸包を見つけるためのグラハムスキャンのデモ

グラハム走査は、平面上の有限点集合の凸包を時間計算量O ( n log n )で求める手法である。この手法は、1972年に元のアルゴリズムを発表したロナルド・グラハムにちなんで名付けられた。 ^{[ 1 ]}このアルゴリズムは、凸包の境界に沿って並べられたすべての頂点を求める。境界上の凹部を効率的に検出し、除去するために スタックを使用する。

アルゴリズム

ご覧の通り、PABとABCは反時計回りですが、BCDは反時計回りではありません。アルゴリズムはこの状況を検出し、反時計回り（この場合はABD）になるまで、以前に選択されたセグメントを破棄します。

このアルゴリズムの最初のステップは、最も低いy座標を持つ点を見つけることです。もし最も低いy座標を持つ点が集合内の複数の点に存在する場合、候補点の中でx座標が最も低い点が選択されます。この点をPとします。このステップにはO ( n )の時間がかかります（nは対象となる点の数）。

次に、点集合を、点Pとx軸とのなす角度の昇順でソートする必要があります。これには、ヒープソート（O( n log n )） などの汎用ソートアルゴリズムが適しています。

角度の順序でソートする場合、角度そのものを計算する必要はありません。区間 内で単調となる角度の関数であれば、どのような関数でも使用できます。コサインは内積を用いて簡単に計算できます。また、直線の傾きを用いることもできます。数値精度が重要な場合は、ソートアルゴリズムで使用される比較関数において、外積の符号を用いて相対的な角度を判定できます。 ${\displaystyle [0,\pi ]}$

複数の点が同じ角度にある場合は、距離を増やして同点を解消するか (点は同じ光線上にあるため、計算を容易にするためにユークリッド距離ではなくマンハッタン距離またはチェビシェフ距離を使用できます)、最も遠い点以外をすべて削除します。

アルゴリズムは、ソートされた配列内の各点を順に検討することで進行します。各点について、まず、その点の直前の2点からの移動が左折か右折かを判断します。右折の場合、最後から2番目の点は凸包の一部ではなく、凸包の「内側」にあります。次に、最新の点と、その点の直前の2点（凸包の内側にあると判断された点）の集合について同じ判断が行われ、「左折」集合に遭遇するまで繰り返されます。「左折」集合に遭遇した時点で、アルゴリズムはソートされた配列内の点集合の次の点（凸包の内側にあると判断された点を除く）に進みます。これらの点を再度検討する必要はありません。（ある段階で3点が同一線上にある場合、それを破棄するか報告するかを選択できます。これは、一部のアプリケーションでは凸包の境界上にあるすべての点を見つける必要があるためです。）

繰り返しになりますが、3点が「左折」か「右折」かを判断するには、2つの線分間の実際の角度を計算する必要はなく、単純な演算だけで実現できます。3点、、について、 2つのベクトルの外積のZ座標を計算します。これは式で与えられます。結果が0の場合、3点は同一直線上にあります。結果が正の場合、3点は「左折」または反時計回りの方向を形成し、そうでない場合は「右折」または時計回りの方向を形成します（反時計回りの番号の付いた点の場合）。 ${\displaystyle P_{1}=(x_{1},y_{1})}$ ${\displaystyle P_{2}=(x_{2},y_{2})}$ ${\displaystyle P_{3}=(x_{3},y_{3})}$ ${\displaystyle {\overrightarrow {P_{1}P_{2}}}}$ ${\displaystyle {\overrightarrow {P_{1}P_{3}}}}$ ${\displaystyle (x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})}$

このプロセスは最終的に開始ポイントに戻り、その時点でアルゴリズムが完了し、スタックには凸包上のポイントが反時計回りの順序で含まれるようになります。

時間計算量

点のソートには、時間計算量が O( n log n ) かかります。ループの時間計算量は、各点について前の点が「右折」しているかどうかをチェックするためO( n ² ) であるように見えるかもしれませんが、実際には各点が最大で 2 回しか考慮されないためO( n ) です。各点は、「左折」の点として（アルゴリズムはその後次の点に進むため）および「右折」の点として（その点は削除されるため）1 回しか出現できません。したがって、ソートにかかる時間が凸包の計算時間の大部分を占めるため、 全体の時間計算量は O( n log n ) になります。${\displaystyle (x_{2},y_{2})}$ ${\displaystyle (x_{3},y_{3})}$ ${\displaystyle (x_{2},y_{2})}$ ${\displaystyle (x_{2},y_{2})}$

擬似コード

以下の擬似コードでは関数 ccw を使用しています。3点が反時計回りに回転する場合は ccw > 0、時計回りの場合は ccw < 0、同一直線上にある場合は ccw = 0 となります。（実際のアプリケーションでは、座標が任意の実数である場合、この関数は浮動小数点数の正確な比較を必要とし、ほぼ同一直線上にある点の数値特異性に注意する必要があります。）

次に、結果を に保存しますstack。

points を点のリスト とし、 stack = empty_stack()とする最も低いy座標と最も左端の点（P0） を見つけ、P0で極角によって点をソートします。複数の点が同じ極角を持つ場合は、最も遠い点のみを保持します。 ポイント単位のポイントの場合: # この点に到達するまで時計回りに回すと、スタックから最後の点がポップされます count stack > 1 かつccw (next_to_top(stack), top(stack), point) <= 0 の場合:スタックを ポップし、ポイントをスタックの 末尾にプッシュします。

これで、スタックには凸包が含まれ、ポイントは反時計回りに向いており、P0 が最初のポイントになります。

ここでは、next_to_top()スタックを変更せずにスタックの先頭から 1 つ下の項目を返す関数と、同様に、top()最上位の要素を返す関数があります。

この疑似コードは、『アルゴリズム入門』から改変したものです。

注記

入力を角度ではなくx座標でソートし、包を2段階で計算して、それぞれ包の上部と下部を生成する場合でも、同じ基本的な考え方が機能します。この修正はAM Andrewによって考案されました。^{[ 2 ]} これはGrahamのスキャンと同じ基本的な性質を持っています。^{[ 3 ]}

グラハムのオリジナルの記述では、凸包の頂点の1つではなく、凸包の内部の点を中心にソートしていました。 ^{[ 1 ]}ソートアルゴリズムのピボットポイントを同じように選択して、グラハムスキャンの残りの手順を実行するのではなく、この点の周りでソートされた順序で他のすべての点を接続すると、入力の多角形化である星型の多角形が生成されます。 ^{[ 4 ]}

グラハムのスキャンで使用されるスタック技術は、すべての最も近い小さな値の問題のスタック技術と非常によく似ており、すべての最も近い小さな値に対する並列アルゴリズムも（グラハムのスキャンのように）ソートされた点のシーケンスの凸包を効率的に計算するために使用できます。^{[ 5 ]}

数値的な堅牢性

数値的堅牢性は、有限精度浮動小数点コンピュータ演算を使用するアルゴリズムで対処すべき問題です。2004 年の論文では、特にグラハム スキャンの実装に使用できる単純な増分戦略を分析しました。^{[ 6 ]}この論文で述べられた目標は、アルゴリズムを具体的に分析することではなく、計算幾何学における浮動小数点計算によって何がどのように失敗する可能性があるかについての教科書的な例を示すことでした。^{[ 6 ]}その後、D. Jiang と NF Stewart ^{[ 7 ]}がこれを詳述し、後方誤差分析を使用して2 つの主要な結論を導きました。1 つ目は、凸包は条件付き問題であるため、妥当な誤差範囲内で答えを生成するアルゴリズムが期待できるということです。第二に、彼らはグラハムスキャンの修正版であるグラハムフォーチュン（数値安定性に関するスティーブンフォーチュンの考えを取り入れたもの^{[ 8 ]}）が有限精度と不正確なデータの問題を「可能な限り」克服することを証明した。

参照

• 凸包アルゴリズム

参考文献

1. Graham, RL (1972). 「有限平面集合の凸包を決定するための効率的なアルゴリズム」(PDF) .情報処理レター. 1 (4): 132– 133. doi : 10.1016/0020-0190(72)90045-2 .
2. Andrew, AM (1979). 「2次元凸包のためのもう一つの効率的なアルゴリズム」.情報処理レター. 9 (5): 216– 219. doi : 10.1016/0020-0190(79)90072-3 .
3. マーク・デ・バーグ;チョン、オトフリート。ヴァン・クレベルド、マーク。オーバーマーズ、マーク (2008)。計算幾何学アルゴリズムとアプリケーション。ベルリン：シュプリンガー。2 ～14ページ 。土井：10.1007/978-3-540-77974-2。ISBN 978-3-540-77973-5。
4. Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph SB; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003). 「点集合の反射性について」. Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (編). Discrete and Computational Geometry: The Goodman-Pollack Festschrift . Algorithms and Combinatorics. Vol. 25. Berlin: Springer. pp.  139– 156. doi : 10.1007/978-3-642-55566-4_6 . ISBN 978-3-642-62442-1. MR  2038472 .
5. Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993). 「最も近い小さな値をすべて見つけることに基づく最適な二重対数並列アルゴリズム」. Journal of Algorithms . 14 (3): 344– 370. CiteSeerX 10.1.1.55.5669 . doi : 10.1006/jagm.1993.1018 . 。
6. Kettner, Lutz; Mehlhorn, Kurt; Pion, Sylvain; Schirra, Stefan; Yap, Chee (2008). 「幾何学計算における堅牢性問題の授業例」(PDF) .計算幾何学. 40 (1): 61– 78. doi : 10.1016/j.comgeo.2007.06.003 .（以前のバージョンは2004年のESA'2004で報告されました）
7. D. JiangとNF Stewart、「計算幾何学における後方誤差解析」、Wayback Machineで2017年8月9日にアーカイブ、計算科学とその応用 - ICCSA 2006コンピュータサイエンス講義ノートシリーズの第3980巻、pp 50–59
8. フォーチュン、スティーブン (1989). 「2次元における点集合三角形分割の安定維持」(PDF) .第30回コンピュータサイエンス基礎シンポジウム. 第30巻. pp.  494– 499. doi : 10.1109/SFCS.1989.63524 . ISBN 0-8186-1982-1. 2013年7月28日時点のオリジナル（PDF）からアーカイブ。

さらに読む

• コーメン, トーマス・H. ;レイサーソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2001) [1990]. 「33.3: 凸包の発見」.アルゴリズム入門（第2版）. MIT Press and McGraw-Hill. pp.  949– 955. ISBN 0-262-03293-7。