Blogopolisから学ぶ計算幾何

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

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

今回から平面走査法という手法による,線分の交差検出について解説します。この手法を使うことで,多数の線分の中から交点を高速に見つけ出すことができます。

はじめに

計算幾何学では,巨大な入力データを扱う可能性を想定して,計算量の少ない効率的なアルゴリズムの追求が行われます。今回からは,線分の集合から交差を検出する問題を取り上げます。平面走査法と呼ばれるアルゴリズムを使用することで,総当たり式の実装に比べ,計算量を大きく削減できることを見ていきます。

多数の線分から交差を見つける

前回,線分を表すLineSegmentクラスを作成し,2つの線分が交差するかどうかを調べるintersects()メソッドや,交点座標を求めるgetIntersectionPoint()メソッドを実装しました。

さて今後,プログラムの扱う線分が100個,1,000個,あるいはそれ以上に増えたときのことを考えてみましょう。これら多数の線分の中から交点を見つけ出すには,どうすれば良いでしょうか。それが今回のテーマです。

線分の交差を示すクラス

まず初めに,線分の交差を表現するクラスを作成しておきましょう。クラス名はIntersectionとし,交差する2つのLineSegmentオブジェクト,segment1とsegment2をフィールドに持たせます。

線分の交差を表現するクラス(Java)

public class Intersection {
    public LineSegment segment1;
    public LineSegment segment2;

    public Intersection(LineSegment segment1, LineSegment segment2) {
        this.segment1 = segment1;
        this.segment2 = segment2;
    }

    public Point2D getIntersectionPoint() {
        return segment1.getIntersectionPoint(segment2);
    }

    @Override
    public String toString() {
        return segment1 + " : " + segment2;
    }
}

さて,今までLineクラスやLineSegmentクラスでは省略してきたequals()メソッドとhashCode()メソッドを,将来のプログラムの都合上,Intersectionクラスでは実装することにします。この2つは,オブジェクトの同値性判定に用いられる,きわめて重要なメソッドです。同値性とequals(),hashCode()の詳細については,[こちらの解説]などを参照してください。

ここでは,線分AとBからなるIntersectionオブジェクトと,線分BとAからなるIntersectionオブジェクトを同値とみなすことにします。すなわち,segment1フィールドとsegment2フィールドを交換しても同値性が保たれるように,equals()メソッドとhashCode()メソッドをオーバーライドします。実装は以下のようになります。

equals()メソッドとhashCode()メソッド(Java)

@Override
public boolean equals(Object obj) {
    if (obj == this) {
        return true;
    } else if (obj instanceof Intersection) {
        Intersection other = (Intersection) obj;
        // segment1とsegment2を交換しても同値性が変わらないようにする
        if (segment1.equals(other.segment1) && segment2.equals(other.segment2)) {
            return true;
        } else if (segment1.equals(other.segment2) && segment2.equals(other.segment1)) {
            return true;
        }
    }
    return false;
}

@Override
public int hashCode() {
    // segment1とsegment2を交換してもハッシュ値が変わらないようにする
    return segment1.hashCode() + segment2.hashCode();
}

交差検出のインターフェース

次に,線分の交差検出を行うIntersectionDetectorインターフェースを作成しておきます。このインターフェースは,線分のリストを入力とし,その中から交差を見つけ,Intersectionオブジェクトのコレクションとして返すexecute()メソッドを持ちます。

IntersectionDetectorインターフェース(Java)

public interface IntersectionDetector {
    Collection<Intersection> execute(List<LineSegment> segments);
}

著者プロフィール

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

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

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

コメント

コメントの記入