まえがき
この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。(この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)
二次元ベクトル
$\overrightarrow{v}$ が二次元ベクトルのとき、$2$ つの実数 $a,b$ を用いて $\overrightarrow{v} = (a,b) $ と表記できます。
$a$ のことを $x$ 成分、$b$ のことを $y$ 成分と呼び、直感的に説明すると、これらの成分は二次元平面上での移動方向と距離を表します。
また、ある $2$ 点を結ぶベクトルの成分は、終端の座標から始点の座標を引いたものです。
特に、始点が原点 $(0,0)$ であるベクトルを位置ベクトルと言います。
Counter Clockwise (ccw)
ある $3$ 点 $A,B,C$ に対して、点 $B$ から見て $A\rightarrow C$ が Counter Clockwise であるということを以下で定義します。
- 点 $A$ が点 $C$ に向かって最短で移動するとき、線分 $BA$ の回転の軌跡が軸 (点 $B$) から見て反時計回りである。
符号付き面積の定義から天下り的に ccw の判定を説明します。線分 $BA$ が通る領域について、符号付き面積 $S\prime$ を以下で定義します。$BA$ が通る領域の面積を $S$ とします。
- $A\rightarrow C$ が ccw ならば $S\prime = S$
- $A\rightarrow C$ が ccw でないならば $S\prime = -S$
線分 $BA$ が通る領域の符号付き面積 $S\prime$ は、$2$ つのベクトル $\overrightarrow{BA},\overrightarrow{BC}$ を並べた $2\times 2$ 行列の行列式を $2$ で割ったものです。
よって $2\times S\prime = {y_c}{x_a} - {y_a}{x_c}$ です。ccw の判定では $S\prime$ の符号にしか興味がないので、$2\times S\prime$ の符号を調べることで $A\rightarrow C$ が ccw かどうか判別することができます。
符号付き面積の $2$ 倍を調べることで、座標が整数の場合に誤差を出さずに ccw の判定ができて嬉しいです。
凸包 (Convex Hull)
$G$ を二次元座標上の点からなる集合とします。
$G$ に対して、凸包を以下で定義します。
- $G$ に属する点を全て辺上または内部に含む最小の凸多角形
この時、凸包の各頂点は $G$ に属する点のいずれかです。逆に、これらの点を計算することが凸包を計算することと言えます。場面によっては、凸包の辺上の点を計算する場合もありますが、本質的な違いはありません。
グラハムスキャン
凸包の下半分の頂点をなす点 $H_1,H_2,H_3,\dots$ を求めるアルゴリズムです。手続きを以下にまとめます。
-
点の集合を $xy$ 座標の 辞書順 の昇順にソートする。ただし $2$ 点 $A,B$ の辞書順の順序は以下で定義される。
- $A,B$ の $x$ 座標が等しいなら、$y$ 座標の順序。
- $A,B$ の $x$ 座標が異なるなら、$x$ 座標の順序。
- はじめ、ソートした点の先頭 $2$ 点を凸包下部の候補として $H$ に追加しておく。
-
残りの点を辞書順に調べ、凸包下部の候補 $H$ に加えていく。このとき新たに追加する点を $P$ とし、以下の手続きを行う。
- 以下の操作で $H$ から候補が除外される限り、以下を繰り返す。
- 点 $P$ を候補に追加した結果、$H$ に含まれる点のうち直近に追加されたものが凸包の頂点に成り得なくなるならば、その点を $H$ から pop する。
- $P$ を $H$ の末尾に追加する。
はじめ、候補 $H$ には辞書順で先頭の $2$ 点が順に格納されています。その後、残りの点を候補 $H$ に追加していく手続きに移ります。
このとき、調べた点 $P$ を候補 $H$ に追加する前に、$H$ の点のうち、この時点で凸包をなし得ない点を、直近に追加されたものから順に pop していきます。
$H$ の末尾の要素 $H\prime$ は、以下が成り立つ場合は凸包に含まれません。
- $H\prime$ から見て、$1$ つ前の $H$ の点から $P$ への最短の移動が ccw である。
次のステップでは候補 $H$ からどの点も除外する必要はありません。
ここで、図の $H_1 \rightarrow P$ の軌跡が $H_2$ を軸として見て時計回りであることも確認できます。
同じ手続きで、$H_4,H_5$ を追加していきます。
次に $H_6$ を追加すると、凸包の頂点に成り得ない点が $H$ から pop されます。
図より、$H_5$ は候補から除外されます。次に $H_4$ を調べた結果、$H_4$ も以下の図より除外されます。いずれも直近 $2$ つの候補と $P$ の ccw に注目して判別します。
残った点たちはこの時点では下に凸なので、$H_3$ は凸包の候補としてキープされます。
このような手続きを繰り返し、最終的に凸包の下側部分 $H$ を得ることができます。
またこのとき、$H$ の点は $xy$ 座標の辞書順でソートされています。
次に、点を $xy$ 座標の辞書順の逆順でソートして、これと同じことを今度は上側領域に対して行います。今度は候補が上に凸である必要があるという点に注意が必要です。
こうして得られた凸包上側の点を $\overline{H}$ とします。また、$\overline{H}$ に含まれる点は $xy$ 座標の辞書順の逆順でソートされています。
なお上側を求める実装は、点の座標全てに $-1$ をかけることで、下側を求めるアルゴリズムを使い回すことができます。ただし再度 $-1$ をかけて元に戻す必要があることに注意してください。
これにて、凸包の上下を求めることができました。
$H$ の末尾と $\overline{H}$ の先頭は同じ点であり、$\overline{H}$ の末尾と $H$ の先頭も同じ点なので、凸包の頂点は、$H,\overline{H}$ それぞれの末尾の要素を pop したものを順に連結した列です。また、こうして得られる列は、凸包の頂点を左下の点 (辞書順最小の点) から反時計回りに並べたものです。