Solving Manhattan Geometry(1)

先日kd-treeについてのエントリを記載したことは、自分にとって計算幾何の面白さを再認識する良い機会となりました。

計算幾何で用いられる幾何学アルゴリズムは比較的若く、今でも進化の過程にあります。また、人間には単純に見える問題も計算機にとっては難しかったり、計算量を減らすために様々なアルゴリズムを応用しなければならないというのも特徴として挙げられます。大変面白い分野であると言えます。


さて、今回取り上げるのはマンハッタン幾何です。マンハッタン幾何は計算幾何の一つ、交差問題に属します。その問題の制限から、幾何学アルゴリズムの中でも初等な問題として取り上げられることが多い様です。この問題は計算幾何の面白さを示す大変良い例であると思います。

さて、マンハッタン幾何は以下の図に示すような水平と垂直の線分によって構成されています。実際にマンハッタンの街路地図がほとんど水平と垂直の線分からなっているため、こう名付けられたそうです。これら直行線分の交差を判定する問題も同様にマンハッタン幾何と呼ばれているようです。

本エントリでは、総当たりによるナイーブなアルゴリズムを取り上げます。実装には、矩形の交差判定アルゴリズムを使用します。このアルゴリズムも大変面白いものであるため、日を改めて解説をしたいと思っています。さらに追って、二分検索木を使った平面走査法によるアルゴリズムを取り上げたいと思います。

さて、ここに挙げた例はAからIまでの9本の線分で構成されています。この程度の問題であれば、人間が見て簡単に交差を列挙することが出来るくらいの複雑度であると言えるでしょう。これらの線分で交差しているものを列挙してみましょう。線分Aは線分D、EおよびHと、また線分Gは線分Eと交差しているのが分かります。


総当たりによる実装はそれほど難しいものでありません。今回はPython3.0で実装してみました。

#!/usr/local/bin/python3.0 -t

from itertools import combinations

def intersect(r1, r2):
    for a, b in zip(zip(*r1), zip(*r2)):
        if max(a) < min(b) or max(b) < min(a):
            return False
    return True

def manhattan(ls):
    for a, b in combinations(ls, 2):
        if intersect(a[0:2], b[0:2]):
            yield a, b

if __name__ == '__main__':
    ls = ((( 70, 211), (274, 211), 'A'),
          ((168, 189), (168, 147), 'B'),
          (( 91, 168), ( 91,  42), 'C'),
          ((147, 330), (147,  84), 'D'),
          ((232, 246), (232,  63), 'E'),
          (( 49, 351), ( 49, 147), 'F'),
          ((189, 105), (351, 105), 'G'),
          ((253, 330), (253, 168), 'H'),
          ((337, 225), (337, 126), 'I'),
          )
    for a, b in manhattan(ls):
        print(a[-1], b[-1])

結果は以下となります。検証した結果と同じですね。

A D
A E
A H
E G


さて、実装を見て行きましょう。線分は端点の座標を納めたタプルと線分のラベルをさらにタプルとして構成しています。点のタプルはx、yの座標値を持っています。例えば、線分Aは以下のようなデータとなります。また、線分Aは水平な線分ですので、y座標が等しいものとなっています。

((70, 211), (274, 211), 'A')

今回のmanhattan関数は、総当たりでの交差判定を行うジェネレータとして実装しています。

from itertools import combinations

def manhattan(ls):
    for a, b in combinations(ls, 2):
        if intersect(a[0:2], b[0:2]):
            yield a, b

itertools.combinationsはPython2.6で追加されたとても便利な関数です。異なるn個のものから異なるm個のものを返すジェネレータとして実装されています。itertools.combinationsを用いない場合の実装は以下のようなものになるのではないでしょうか。

def manhattan(ls):
    for i in range(len(ls)-1):
        for j in range(i+1, len(ls)):
            if intersect(ls[i][0:2], ls[j][0:2]):
                yield ls[i], ls[j]

この実装を見て選択ソートの実装を思い浮かんだ方もいるのではないかと思います。ここで計算量を考えてみましょう。


総当たりによる交差判定の回数は、重複を持たない組み合わせの数として算出することが出来ます。

今回は異なるn個のものから異なる2個のものを選んでいるため、mは2となります。

この式から、このアルゴリズムの計算量がO(n^2)であることが分かります。これは選択ソートと同様の計算量です。また、データ量が増えれば増えるほど、爆発的に計算量が増すアルゴリズムであると言えます。

今回の例に挙げた9組の線分の総当たりの交差判定の計算量は、以下のように算出出来ます。

10倍の90組の線分の総当たりに要する計算量は、以下となります。計算量の増加は111.25倍ですので、指数的に増えていることが分かります。

余談ですが、Python3.0で検算するには以下とします。

>>> from itertools import combinations
>>> len(tuple(combinations(range(90), 2)))
4005


さて、残るはintersect関数です。今回用いた線分のデータ構造は、xもしくはy座標方向に縮退した矩形とみなすことが出来ます。そのため、矩形の交差判定アルゴリズムをそのまま使用しています。

def intersect(r1, r2):
    for a, b in zip(zip(*r1), zip(*r2)):
        if max(a) < min(b) or max(b) < min(a):
            return False
    return True

矩形の交差判定も大変面白いアルゴリズムです。次回のエントリではマンハッタン幾何から一旦離れ、矩形の交差判定について取り上げてみたいと思っています。

アルゴリズムC〈第2巻〉探索・文字列・計算幾何

アルゴリズムC〈第2巻〉探索・文字列・計算幾何