Blogopolisから学ぶ計算幾何

第9回 凸多角形の交差計算(前編)

この記事を読むのに必要な時間:およそ 2 分

凸多角形の交差計算におけるステータス

線分の交差検出の場合,ステータスには順序付き集合が使われました。しかし,凸多角形の交差計算では,ステータスにはもっとシンプルな構造を用いることができます。なぜなら,1つの凸多角形が走査線と交わるとき,その交差は図5に示すように,たかだか,凸多角形の「左側」にある辺と「右側」にある辺の2つに限定されるからです。計算の入力となるのは2つの凸多角形ですから,走査線と交わる線分の数は,最大でも4つにしかなりません。

図5 凸多角形と走査線の交差回数

図5 凸多角形と走査線の交差回数

入力の凸多角形をc1, c2とすると,c1の「左側」の辺を指すポインタleft_edge_c1,⁠右側」の辺を指すポインタright_edge_c1を用意し,さらにc2についても同様にleft_edge_c2とright_edge_c2を用意すれば,この4つのポインタだけでステータスを表現できることになります(図6⁠⁠。

図6 4個のポインタによるステータスの表現

図6 4個のポインタによるステータスの表現

順序付き集合の操作には,log(n)のオーダーで計算時間がかかっていました。これに対して,4個のポインタを使った場合,ステータスの計算は定数時間で実行できてしまうため,速度面でも有利になります。

凸多角形の交差計算におけるイベントキュー

次に,イベントキューについて考えます。線分の交差検出では,計算途中で交点イベントが動的に生成されるため,キューに対するイベントの追加や取り出しの操作を高速に実行できるよう,ステータスと同様に順序付き集合が使われました。

これに対して,凸多角形の交差計算ではイベントの考え方がやや異なり,交点イベントは用いません。したがって,走査線が移動すべき次のイベント位置を求めるには,left_edge_c1, right_edge_c1, left_edge_c2, right_edge_c2の各下端点のうち,もっとも上に存在する点を調べれば十分です。イベントキューの存在意義は,次に処理するイベント点を見つけることなので,凸多角形の交差計算では,イベントキューをわざわざ用意する必要がないのです。

もう少し詳しく述べると,平面走査法による凸多角形の交差計算において,走査線を次の位置に移動させる処理は,以下のように実行することができます。

  • 1.辺ポインタleft_edge_c1, right_edge_c1, left_edge_c2, right_edge_c2の中から,下の端点がもっとも上に存在するものを選ぶ。
  • 2.選択された辺ポインタを,その下端点に接続する次の辺を指すように更新する。

このように,凸多角形の交差計算における平面走査法ではイベントキューを使わないことから,イベントキューの操作に必要だったlog(n)の計算時間も削減できることになります。

まとめと次回予告

今回は,図形のブーリアン演算の中でも比較的容易に実装することのできる,凸多角形の交差計算を紹介しました。また,この計算には線分の交差検出の際に用いた平面走査法が応用できることを示し,線分の交差検出に比べ,ステータスやイベントキューがより単純なデータ構造で表現できることを説明しました。

次回は,平面走査法を使った凸多角形の交差計算において,イベントが発生したときどのような処理を行えば良いかを見ていきます。お楽しみに!

著者プロフィール

浜本階生(はまもとかいせい)

1981年生まれ。栃木県出身。東京工業大学情報工学科卒業。技術やアイデアの組み合わせから面白いソフトウェアを生み出したいと日々考えている。現在,ブログの解析および視覚化の試みとして「TopHatenar」「Blogopolis」を開発,運用中。

URLhttp://d.hatena.ne.jp/kaiseh/