Blogopolisから学ぶ計算幾何

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

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

総当たり法による交差検出

では,IntersectionDetectorインターフェースをどのように実装すれば良いか考えてみましょう。最も単純な答えは,総当たり(brute-force)方式です。すなわち,線分A,B,C…が与えられたら,AとB,AとC,BとC…というように,すべての線分の組み合わせを列挙して,それぞれ交差判定を行う方法です。

この総当たり法を実装したものが,以下のBruteForceIntersectionDetectorクラスです。

総当たり法の実装(BruteForceIntersectionDetectorクラス,Java)

public class BruteForceIntersectionDetector implements IntersectionDetector {
    public Collection<Intersection> execute(List<LineSegment> segments) {
        List<Intersection> result = new ArrayList<Intersection>();
        int size = segments.size();
        for (int i = 0; i < size; i++) {
            LineSegment s1 = segments.get(i);
            // j < iの場合は調査済み,またj = iの場合は2線分が同一となり交差を調べる
            // 必要がないため,j = i + 1からループを開始する
            for (int j = i + 1; j < size; j++) {
                LineSegment s2 = segments.get(j);
                if (s1.intersects(s2)) {
                    result.add(new Intersection(s1, s2));
                }
            }
        }
        return result;
    }
}

コードを見ると分かるように,入力の線分の個数をnとすると,n回のループが実行され,それらの中でさらにn-1回,n-2回…のループが実行されるため,全体として,

回の交差判定が行われることになります。この計算量は

となります。

線分の数が少ないうちは,総当たり法でもまったく問題ありません。しかし,線分が数万,数十万の規模になると,莫大な計算量が必要になり,総当たり法は現実的でなくなってきます。

そんなに多くの線分を扱うケースなんてあるの?と思うかもしれません。しかし例えば,Blogopolisのデータベースにはおよそ70万個の多角形データが格納されており,多角形の平均角数を4とすれば,約300万個の線分を扱っていることになります。

図1 Blogopolisと線分

図1 Blogopolisと線分

さらに,日本や世界の国土情報を扱う地理情報システム(GIS)を考えると,Blogopolisとは桁違いの座標データを保持していることが容易に想像できます。計算幾何学では,こうした環境でも現実的な時間で計算を実行できるアルゴリズムが求められるのです。

平面走査法

総当たり法のどこに無駄があるのか,図2を例に考えてみましょう。図2では,線分s1とs2に対して,s3, s4, s5が大きく下方に離れています。直感的にいって,s3とs4は近くにあるため,交差を判定する価値がありそうですが,s1とs3の交差を判定するのは(両者が明らかに離れているため)無駄に思えます。

図2 多数の線分からの交差検出

図2 多数の線分からの交差検出

こうした線分同士の「近さ」を考慮に入れて,計算を効率化するにはどうすれば良いのでしょうか。ここで登場するのが,平面走査法(plane sweep algorithm)という考え方です。平面走査法では,x軸に平行な直線を走査線(sweep line)として仮想的に設定し,少しずつ下へと動かしていきます図3⁠。

図3 平面走査法

図3 平面走査法

平面走査法では,現在の走査線と交わる線分だけに注目します。たとえば,図3で走査線が(A)の位置にあるときには,s1とs2の交差のみをチェックします。その後走査線が下に移動し,(B)の位置まで来たときには,s3とs4の交差のみをチェックします。このように,走査線を基準にして計算範囲を限定することで,計算量を大きく削減できる可能性が生まれるのです。

平面走査法の具体的な実装については,次回に譲ることにしましょう。

まとめと次回予告

今回は,線分の集合から交差を見つけるアルゴリズムについて考察しました。線分の交差を表現するクラスと交差検出のインターフェースを用意し,総当たり法による実装を行いました。さらに,総当たり法の計算量を改善するための考え方として,平面走査法の概念を紹介しました。

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

次回は,平面走査法の詳細に立ち入っていきます。お楽しみに!

著者プロフィール

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

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

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