Blogopolisから学ぶ計算幾何

第5回 平面走査法による線分の交差検出(後編)

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

はじめに

前々回前回と,平面走査法による線分交差検出について説明してきました。今回はその仕上げとして,いよいよ平面走査法のアルゴリズムの実装に挑戦します。

前回の復習

まず,前回導入した,平面走査法に必要な3つのデータ構造を復習しておきましょう。

  • イベントは,線分の始点と終点,そして交点に対応するオブジェクトです。前回は,イベントを表現するEventクラスを作成しました。
  • イベントキューは,イベントを要素とするコレクションです。キューの要素は,イベント点のy座標が小さい順に,常にソートされています。前回,イベントキューには,java.util.TreeSetクラスを利用することを説明しました。
  • ステータスは,現在の走査線と交わる線分を要素とするコレクションです。ステータスの要素は,走査線と線分の交点のx座標が小さい順に,常にソートされています。ステータスにもTreeSetクラスを利用します。

この3つを使って交差検出のアルゴリズムを組み立てることが,今回のテーマになります。

イベントの処理

イベントキューには,未処理のイベント点が上から順番に格納されています。走査線を次のイベント点の位置まで動かす操作は,イベントキューから先頭の(最小のy座標を持つ)イベントを取り出す作業に対応します。

さて,こうしてイベントを取り出した後は,そのイベントに関してどんな処理を実行すれば良いのでしょうか。イベントの種類ごとに見ていきましょう。

始点イベントの処理

始点イベントをきっかけとして,その始点を持つ線分(Sstartとします)は,走査線と交わり始めます。したがって,Sstartをステータスに挿入する必要があります。

さらにこのとき,Sstartと以下の線分の交差をチェックします。

  • ステータス中でSstartの直前(左隣)に位置する線分(Sl
  • ステータス中でSstartの直後(右隣)に位置する線分(Sr

もし交差する場合には,その交点イベントを新しく作成し,イベントキューに登録します。

図1は始点イベントの例です。この図の場合,SstartとSrの交差が検出されます(赤い交点)⁠

図1 始点イベント

図1 始点イベント

交点イベントの処理

交点イベントには,交差する2つの線分が関わります。この2線分のうち,交点通過前の走査線上で左にあった線分をS'l右にあった線分をS'rとします。

交点を境にして,S'lとS'rの走査線上の位置関係は逆転し,S'lが右に,S'rが左に来るようになります。したがって,ステータス上でのS'lとS'rの位置を入れ替える必要があります。

このとき,ステータスの線分の隣接関係が変化した部分に関して,以下の交差をチェックします。

  • 元のステータス中でS'lの直前(左隣)に位置した線分とS'r
  • 元のステータス中でS'rの直後(右隣)に位置した線分とS'l

それぞれ,交差する場合には,始点イベントでの交点検出時と同様に,交点イベントを作成してイベントキューに登録します図2)⁠

図2 交点イベント

図2 交点イベント

終点イベントの処理

走査線が終点イベントに着くと,その終点を持つ線分(Sendとします)は,今後走査線と交わらなくなります。したがって,Sendをスタータスから削除する必要があります。

ここで,以下の線分を考えます。

  • ステータス中でSendの直前(左隣)に位置する線分(S''l
  • ステータス中でSendの直後(右隣)に位置する線分(S''r

S''lとS''rはこれまで,ステータス上で離れた位置にありました。しかし,Sendを削除したことによって,今後は隣接するようになります。したがって,このS''lとS''rの交差を新たにチェックし,交差する場合には交点イベントを作成・登録します図3)⁠

図3 終点イベント

図3 終点イベント

以上をまとめると,表1のようになります。

表1 イベントの処理

種類ステータスの変更交差チェック対象
始点線分を挿入挿入した線分とその左隣/右隣
交点2線分の位置を交換新しく左に来る線分とその左隣/新しく右に来る線分とその右隣
終点線分を削除削除する線分の左隣と右隣

著者プロフィール

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

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

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

コメント

コメントの記入