Blogopolisから学ぶ計算幾何

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

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

順序付き集合:TreeSetクラス

イベントキューとステータスのところで,順序付き集合という言葉が出てきました。順序付き集合とは,特定の順序関係にしたがって,要素が常にソートされている集合です。Javaでこの要請をみたすクラスは,java.util.TreeSetです。TreeSetは,赤黒木(red-black tree)と呼ばれる平衡二分木で実装されており,以下のようなメソッドが利用できます。

add(element)
集合にelementを追加します。
remove(element)
集合からelementを削除します。
pollFirst() - Java 6以降
先頭(最小)の要素を取得し,その要素を集合から削除します。集合が空の場合はnullを返します。
lower(element) - Java 6以降
elementよりも小さい要素のうち,最大のものを返します。elementよりも小さい要素が存在しない場合はnullを返します。
higher(element) - Java 6以降
elementよりも大きい要素のうち,最小のものを返します。elementよりも大きい要素が存在しない場合はnullを返します。

TreeSetクラスの非常に重要な特徴は,上記のメソッドすべてがlog(n)時間で実行できることです。本連載では,イベントキューとステータスの両方にTreeSetを使用します。TreeSetの詳細は,こちらのAPIドキュメントを参照してください。

イベントクラス

それでは,イベントクラスを用意しましょう。Eventクラスは,Comparableインターフェースを実装することで,イベントキューに格納するときの順序関係(y座標順)を定義します。

Eventクラス(Java)

public class Event implements Comparable<Event> {
    public enum Type { // イベントの種類
        SEGMENT_START, // 線分の始点
        SEGMENT_END,   // 線分の終点
        INTERSECTION   // 線分同士の交差
    }

    public Type type;
    public double x;
    public double y;
    // 点に関連する線分1
    public LineSegment segment1;
    // 点に関連する線分2(type = INTERSECTIONのときのみ使用)
    public LineSegment segment2;

    public Event(Type type, double x, double y, LineSegment segment1,
            LineSegment segment2) {
        this.type = type;
        this.x = x;
        this.y = y;
        this.segment1 = segment1;
        this.segment2 = segment2;
    }

    // Comparable<Event>>の実装
    public int compareTo(Event e) {
        int c = Double.compare(y, e.y); // イベント点のy座標を比較
        if (c == 0) { // y座標が等しい場合はx座標を比較
            c = Double.compare(x, e.x);
        }
        return c;
    }
}

走査線ベースの線分コンパレータ

次に,ステータスで必要となる,走査線と線分の交点のx座標にもとづく順序の比較を,SweepLineBasedComparatorクラスとして作成しましょう。これは,Comparatorインターフェースを実装したコンパレータ(比較子)になります。

SweepLineBasedComparatorクラスを作成するときに注意が必要なのは,2つ以上の線分が走査線の位置でちょうど交差するとき,どう順序を付けるかです。この場合,走査線の下に伸びた線分を見て,より左に位置する方の線分が小さいものとします。

以上のルールを実装したものが,次のコードになります。

SweepLineBaseComparatorクラス(Java)

public class SweepLineBasedComparator implements Comparator<LineSegment> {
    private Line sweepLine;
    private Line belowLine;

    public SweepLineBasedComparator() {
        setY(0);
    }

    // 走査線のy座標を更新
    public void setY(double y) {
        // 走査線を更新
        sweepLine = Line.fromPoints(0, y, 1, y);
        // 走査線の少し下を通る線を作成
        belowLine = Line.fromPoints(0, y + 0.1, 1, y + 0.1);
    }

    // Comparator<LineSegment>の実装
    public int compare(LineSegment s1, LineSegment s2) {
        int c = compareByLine(s1, s2, sweepLine);
        if (c == 0) { // 走査線上の交点が等しい場合は,走査線の少し下の位置で比較
            c = compareByLine(s1, s2, belowLine);
        }
        return c;
    }

    // s1とs2を,lineとの交点のx座標にもとづいて比較
    private int compareByLine(LineSegment s1, LineSegment s2, Line line) {
        Point2D p1 = s1.toLine().getIntersectionPoint(line);
        Point2D p2 = s2.toLine().getIntersectionPoint(line);
        // 交点がnull(線分とlineが平行)の場合は線分の1端点を比較値に採用
        double x1 = p1 != null ? p1.getX() : s1.x1;
        double x2 = p2 != null ? p2.getX() : s2.x1;
        return Double.compare(x1, x2);
    }
}

上のコードで,compareByLine()メソッドに走査線と平行な線分が渡された場合,走査線と線分の交点が存在しないため,比較用のx座標が得られません(p1またはp2がnullになる⁠⁠。この場合は,代用の値として線分の1端点のx座標(LineSegment#x1)を使用しています。

まとめと次回予告

今回は,平面走査法による線分の交差検出の詳細を解説し,イベント,イベントキュー,ステータスの3つのデータ構造を導入しました。また,イベントキューとステータスに使用する順序付き集合としてTreeSetクラスを説明しました。さらに,ステータス上の順序関係を定義する線分のコンパレータも作成しました。

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

次回は,今回のデータ構造を土台として,平面走査法のアルゴリズムを実装します。お楽しみに!

著者プロフィール

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

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

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