Blogopolisから学ぶ計算幾何

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

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

はじめに

今回は,平面走査法による線分交差検出のデータ構造を実装していきます。内容がかなり難しくなってきますが,説明とソースコードを納得できるまで読み返していただければと思います。

平面走査法と水平方向

前回は,多数の線分から交差を検出する方法として,平面走査法(plane sweep algorithm)の考え方を紹介しました。これは,x軸に平行な走査線を上から下へと動かしていき,走査線と交わる線分のみを計算対象とすることで,交差検出の計算量を減らすというものでした図1)⁠

図1 平面走査法

図1 平面走査法

実は,これだけでは考え方としてまだ不足なのです。図2を見てください。図2では図1と違い,すべての線分が同じくらいのy座標範囲にまとまって存在しています。こうした場合,走査線が多数の線分と交わる時間が大半を占めるため,計算量をほとんど削減できないことになってしまいます。

図2 走査線と多数の線分の交差

図2 走査線と多数の線分の交差

この状況を改善するには,走査線で垂直方向の計算範囲を限定することに加えて,水平方向にも計算の局所性を持たせる必要があります。具体的には,走査線と線分の交点のx座標を基準にして,水平方向に隣接した線分同士の交差のみをチェックするのです。この様子を図3に示します。

図3 走査線とx座標を両方考慮した交差検出

図3 走査線とx座標を両方考慮した交差検出

平面走査法のデータ構造

以上が,平面走査法による線分交差検出の概要です。このアルゴリズムを実装していくわけですが,まず初めに,アルゴリズムで用いるデータ構造を3つ導入します。3つのデータ構造とは,イベント,イベントキュー,そしてステータスです。

なお,今回からは図4のように,y座標が上から下に向かって増加する座標系を採用します。

図4 座標系

図4 座標系

イベント

走査線は上から下まで動かすと先に述べました。しかし,実際のアルゴリズムでは連続的に動かすわけではなく,特定のイベント点を単位として,離散的に位置を変化させることになります。

イベント点になるのは,アルゴリズムの入力となるすべての線分の端点,そして,計算途中で検出された線分同士の交点です。計算の開始時点では,線分の端点に対応するイベントのみが存在しますが,走査線が移動し,新たな交点が見つかるたびに,交点に対応するイベントが生成されていきます。

イベントオブジェクトは,そのイベント点の座標と,点の種類(線分の始点,線分の終点,線分同士の交点のいずれか)を保持します。さらに,点に関連する線分(始点または終点イベントの場合はその線分,交点イベントの場合は交差する2線分)も合わせて保持します。

イベントキュー

イベントキューは,イベントの順序付き集合です。ここでの順序は,イベントのy座標の大小関係にもとづいて定義され,イベントキューの先頭位置にあるイベントはキューの中で最小のy座標を持ちます。走査線を現在の位置から次の位置へと移動する処理は,イベントキューから先頭のイベントを取り出す作業に相当します。

ステータス

ステータスは,現在の走査線と交差するすべての線分の順序付き集合です。ここでの順序は,走査線と各線分の交点のx座標の大小関係にもとづいて定義されます。この順序関係は,走査線の移動にともなって動的に変化します。例えば,図5で走査線が(A)の位置にあるとき,ステータスは(s1, s2, s3, s4)の順序を保持していますが,走査線が(B)まで下がると,順序は(s1, s3, s2, s4)に変化します。

図5 ステータス

図5 ステータス

著者プロフィール

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

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

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

コメント

  • compare

    compare あたりで分からなくなりました。

    c/c++, fortranで書けるような分かりやすいサイトがあれば教えてください。

    Commented : #1  inomata@nalux.co.jp (2017/11/01, 13:22)

コメントの記入