2009-06-23

先日のエントリでは、矩形の交差判定を行う際の用語の紹介を行いました。今回のエントリでは、射影(Projection)という技法を紹介します。

一見、射影は単純なことを難しく表現しているだけに感じられるかもしれません。しかし、計算幾何や領域検索を考えるにあたり必ず押さえておきたい技法であると思います。名著アルゴリズム Cの計算幾何の章には、領域検索の初等的な方法として紹介されています。その解説があまりにも見事ですので、今回のエントリではそれを元に解説したいと思います。

以下の図に示すような、与えられた矩形に含まれる点を検索する問題を考えてみましょう。点群は、A〜Pとしてラベルが与えられた16個のものであるとします。

この矩形は、先日解説したAABBであることを意識しておいてください。

このような二次元の点集合に対して効率よく領域検索を行うアルゴリズムは数多く考案されています。先日可視を試みたkd木もこのような領域検索を効率良く扱うデータ構造であり、アルゴリズムでした。今回はそのような技巧的なアルゴリズムから離れ、初等的な方法を用いた領域検索を考えてみます。

初めに思い描くのは、逐次検索(Sequencial Search)によるものでしょう。点を逐一選択し、矩形に含まれるか否か総当たりに判定するアルゴリズムです。Pythonで実装するのも簡単です。今回の実装では解説のため、あえて冗長な記述をしています。

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

if __name__ == '__main__':
    ps = (( 84, 211, 'A'),
          (253,  49, 'B'),
          (147, 189, 'C'),
          (105,  84, 'D'),
          (126, 330, 'E'),
          (189, 253, 'F'),
          ( 49, 147, 'G'),
          (168, 105, 'H'),
          (211, 168, 'I'),
          (309, 126, 'J'),
          (232, 281, 'K'),
          (351, 316, 'L'),
          (330,  70, 'M'),
          (288, 351, 'N'),
          ( 70, 267, 'O'),
          (274, 232, 'P'),
          )

    r = ((126, 232),
         (211, 351))

    for p in (p
              for p in ps
              if min(r[0][0], r[1][0]) <= p[0] <= max(r[0][0], r[1][0]) and \
                 min(r[0][1], r[1][1]) <= p[1] <= max(r[0][1], r[1][1])):
        print(p[-1])

今回も実装にPython3.0を用いています。また、矩形には対角をなす2点を与えています。詳細には、矩形の左下、右上もしくは左上、右下の点の対を与えます。

出力結果は以下のようになります。

E
F

点群はA〜Pの16個でした。最適化にもよりますが、上記の逐次検索ではx軸に対する包有判定を16回、またy軸に対する包有判定を同じく16回行うことが分かります。

さて、この判定は全て、本当に必要なのでしょうか?

ここで、点と矩形の包有判定について考えてみましょう。点と矩形のx軸に対する包有判定が偽であった場合、点が矩形に含まれないことはy軸に対する包有判定をするまでもなく明らかです。またこれは、包有判定を判定が行われる次元のそれぞれに適用することが出来ることを示しています。

この技法を、射影(Projection)と呼びます。

では、射影の考え方を先ほどの実装にもう少し取り入れてみましょう。

    for p in (p
              for p in (p
                        for p in ps
                        if min(r[0][0], r[1][0]) <= p[0] <= max(r[0][0], r[1][0]))
              if min(r[0][1], r[1][1]) <= p[1] <= max(r[0][1], r[1][1])):
        print(p[-1])

内側の内包表記でx軸に射影した値を用いて包有判定を行い、点群を絞り込みます。x軸での包有判定が真となるのは点C、E、F、HおよびIのみとなります。そのため、外側の内包表記にはわずか5点しか渡されていないことになります。その結果、32回の包有判定を21回に減らすことが出来ました。

領域検索問題に対して射影という技法を用いるもう一つの利点は、予め確立的な予想を立てることが出来ることが挙げられます。

点が全体に一様に分布していると仮定すると、調べるべき点の数の平均値も簡単に予想できます。例えば、この図では矩形の面積の割り合いは全体の面積に対して約1/16となっています。そのため、矩形に含まれる点の割り合いの期待値も約1/16と予想を立てることが出来ます。言い換えれば、逐次検索で行った包有判定の実に15/16は無駄になることも予想出来る、ということです。

さて、射影を用いた場合の確立的な予想を考えてみます。例に示す矩形の幅と高さの全体の幅と高さに対するそれぞれの割り合いは約1/5と約3/10です。目的は無駄なテストを減らすことですので、この割り合いが小さい軸への射影と包有判定を先に行ったほうが効率がよいことが分かります。

そのため、この例の場合、x軸での射影と包有判定を優先したほうが効率的であると判断出来ます。その結果、y軸への射影を行う段階ですでに約4/5の点群を包有判定の対象から除外することが出来ると予想できます。

より極端な例も示しておきましょう。以下の例では、矩形の幅と高さの割合はそれぞれ、約9/10と約3/10となります。y軸への射影と包有判定を優先した場合、70%の点群は予め除外されると期待出来ます。逆に、x軸への射影と包有判定を優先した場合、ほとんどの点群は手つかずのままy軸への射影と包有判定に渡されることが予想出来ますので、領域検索全体として、効率が悪くなるであろうことが予め分かります。