Blogopolisから学ぶ計算幾何

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

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

平面走査法の実装

それでは,ここまで解説してきたアルゴリズムをコーディングしてみましょう。IntersectionDetectorインターフェースを実装するPlaneSweepIntersectionDetectorクラスを,以下のように作成します。

リスト1 PlaneSweepIntersectionDetectorクラス(Java)

public class PlaneSweepIntersectionDetector implements IntersectionDetector {
    public Collection<Intersection> execute(List<LineSegment> segments) {
        // イベントキューを作成
        TreeSet<Event> eventQueue = new TreeSet<Event>();

        for (LineSegment s : segments) {
            // 線分の端点のうち上にある方を始点,下にある方を終点としてイベントを登録
            // 線分が水平な場合は左の端点を始点とする
            if (s.y1 < s.y2 || (s.y1 == s.y2 && s.x1 < s.x2)) {
                eventQueue.add(new Event(Event.Type.SEGMENT_START, s.x1, s.y1, s, null));
                eventQueue.add(new Event(Event.Type.SEGMENT_END, s.x2, s.y2, s, null));
            } else {
                eventQueue.add(new Event(Event.Type.SEGMENT_START, s.x2, s.y2, s, null));
                eventQueue.add(new Event(Event.Type.SEGMENT_END, s.x1, s.y1, s, null));
            }
        }

        SweepLineBasedComparator sweepComparator = new SweepLineBasedComparator();
        // ステータスを作成。要素の順序関係はsweepComparatorにしたがう
        TreeSet<LineSegment> status = new TreeSet<LineSegment>(sweepComparator);

        // 今回の実装では同一の交点が複数回検出される可能性があるため,HashSetを使って重複を防ぐ
        Collection<Intersection> result = new HashSet<Intersection>();

        Event event;
        // キューから先頭のイベントを取り出す
        while ((event = eventQueue.pollFirst()) != null) {
            double sweepY = event.y;
            switch (event.type) {
            case SEGMENT_START: // 始点イベントの場合
                sweepComparator.setY(sweepY); // 走査線を更新

                LineSegment newSegment = event.segment1;
                status.add(newSegment); // ステータスに線分を追加

                LineSegment left = status.lower(newSegment);
                LineSegment right = status.higher(newSegment);
                // 左隣の線分との交差を調べる
                checkIntersection(left, newSegment, sweepY, eventQueue);
                // 右隣の線分との交差を調べる
                checkIntersection(newSegment, right, sweepY, eventQueue);
                break;
            case INTERSECTION: // 交点イベントの場合
                left = event.segment1;
                right = event.segment2;
                // 交点を戻り値に追加
                result.add(new Intersection(left, right));

                LineSegment moreLeft = status.lower(left);
                LineSegment moreRight = status.higher(right);

                // ステータス中のleftとrightの位置を交換するため,いったん削除する
                status.remove(left);
                status.remove(right);
                sweepComparator.setY(sweepY); // 走査線を更新
                // 計算誤差により,走査線の更新後も順序が交換されない場合は
                // 走査線を少し下げて順序が確実に変わるようにする
                if (sweepComparator.compare(left, right) < 0) {
                    sweepComparator.setY(sweepY + 0.001);
                }
                // 更新後の走査線を基準としてleftとrightを再追加(位置が交換される)
                status.add(left);
                status.add(right);

                // right(位置交換によって新しく左側に来た線分)と,そのさらに左隣の線分の交差を調べる
                checkIntersection(moreLeft, right, sweepY, eventQueue);
                // left(位置交換によって新しく右側に来た線分)と,そのさらに右隣の線分の交差を調べる
                checkIntersection(left, moreRight, sweepY, eventQueue);
                break;
            case SEGMENT_END: // 終点イベントの場合
                LineSegment endSegment = event.segment1;
                left = status.lower(endSegment);
                right = status.higher(endSegment);

                // 線分の削除によって新しく隣り合う2線分の交差を調べる
                checkIntersection(left, right, sweepY, eventQueue);
                status.remove(endSegment); // ステータスから線分を削除

                sweepComparator.setY(sweepY); // 走査線を更新
                break;
            }
        }

        return result;
    }

    // 線分leftとrightが走査線の下で交差するかどうか調べ,交差する場合は交点イベントを登録する
    private void checkIntersection(LineSegment left, LineSegment right,
            double sweepY, TreeSet<Event> eventQueue) {
        // 2線分のうち少なくとも一方が存在しない場合,何もしない
        if (left == null || right == null) {
            return;
        }
        Point2D p = left.getIntersectionPoint(right);
        // 交点が走査線よりも下に存在するときのみ,キューに交点イベントを登録
        if (p != null && p.getY() >= sweepY) {
            eventQueue.add(new Event(Event.Type.INTERSECTION, p.getX(), p
                    .getY(), left, right));
        }
    }
}

プログラムではまず,与えられたすべての線分について始点イベントと終点イベントを作成し,イベントキューに登録しています。このとき,線分の2端点のうち,上にある方を始点,下にある方を終点としています。こうしてイベントキューを初期化したら,後はイベントを先頭から1つずつ取り出し,表1にしたがって処理を行っていきます。イベントが全部消化され,イベントキューが空になったとき,すべての交差が戻り値として得られていることになります。

ただし,今回の実装ではプログラムを簡潔にするため,3つ以上の線分が1点で交わるなどの例外的な状況は考慮していません。

平面走査法の計算量

平面走査法による線分交差検出の計算量は,入力となる線分の数をn,交点の数をkとすると

図4

図4

で表されます。交点数に依存した計算量となるため,全ての線分が互いに交わっているような,極端に「こんがらがった」配置に対しては,かえって遅くなってしまいます。しかし,交点検出が必要になる実際の状況では,せいぜい線分数に比例する程度の交点しか存在しないことが一般的なので,前々回で実装した総当たり法よりも計算量を大きく削減できることになります。

デモプログラム

今回解説したアルゴリズムをグラフィカルに動作確認できるよう,Swingアプリケーションのデモプログラムを用意しました。Java Web Start形式になっており, こちらをクリックして直接起動できます。ソースコードは紙面には掲載しませんので,アーカイブをダウンロードして確認してください。

デモプログラムを起動すると,キャンバスにいくつかの線分が表示されます。⁠移動」⁠追加」⁠削除」のツールボタンを選択し,キャンバス上でマウスクリックやドラッグをすることで,線分を自由に追加したり,動かしたりすることができます。⁠次のイベント」ボタンをクリックすると,走査線が次のイベント点まで移動し,イベント点に関係する線分や,このとき検出される交点が強調表示されます。線分の配置をいろいろと変更し,処理の流れを追ってみてください。

まとめと次回予告

今回は,平面走査法による線分交差検出の完全な実装を行いました。走査線を少しずつ動かしていくという平面走査法の発想は,交差の検出に限らず,平面幾何のさまざまな問題に広く適用できますので,ぜひ覚えておいてください。

今回作成したプログラムのソースコードがダウンロードできます。

次回からは,線分を連結して作られる凸状の多角形について考えていきます。お楽しみに!

著者プロフィール

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

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

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