Axis Aligned Rectangle Intersection and Projection Technique(3)

さて、先日までのエントリにて矩形と射影について各々解説しました。今回のエントリでは、射影を応用した矩形の交差判定について記載したいと思います。

早速、以下のようなAとBの二つの矩形の交差判定について考えてみましょう。先日のエントリにて解説したのと同様に、矩形には対角をなす2点を与えるものとします。具体的には、矩形の左下、右上もしくは左上、右下の点の対を与えます。


矩形の交差判定は射影と大変相性がよいアルゴリズムと言えます。射影により、矩形の交差判定は複数の線分の交差判定に置き換えることが出来ます。具体的には、まず矩形をx軸に射影した線分の交差判定を行い、次にy軸に射影した線分の交差判定を行います。また、x軸に射影した線分の交差判定が偽であった場合、y軸に射影した線分の交差判定を行うまでもなく、矩形は交差しないであろうことが判断出来ます。


さて、では線分の交差判定を考えてみましょう。矩形AおよびBをx軸に射影した線分を用いて考えることにします。

線分の交差判定は以下の条件が成り立つか否かを調べることによって判定します。この条件はWikipediaなどでも紹介されている一般的なものであり、交差判定について記載している文書によく見受けられるものです。

何故この条件を満たすと線分が交差するか、今ひとつ理解出来ませんね。ここで、条件を可視してみましょう。二つの線分を構成する四つの点がそれぞれ重ならないとすると線分の組み合わせは6つとなります。また、交差判定を多次元に拡張した際のことを考慮して、それぞれの変数にiを添えています。

なるほど、確かに交差を判定出来ているようです。しかし、私はこの条件があまり好きではありません。今一つ覚えられないのです。後ほどこの条件を整理していきますが、その結果に得た条件のほうが直感的に感じます。


さておき、まず線分の交差判定をPythonで実装してみましょう。今回もPython3.0を使用しています。

def intersect(a, b):
    return min(a) <= max(b) and min(b) <= max(a):

なかなかシンプルですね。では、矩形、すなわち二次元での交差判定を実装してみましょう。

def intersect(A, B):
    return min(A[0][0], A[1][0]) <= max(B[0][0], B[1][0]) and \
           min(B[0][0], B[1][0]) <= max(A[0][0], A[1][0]) and \
           min(A[0][1], A[1][1]) <= max(B[0][1], B[1][1]) and \
           min(B[0][1], B[1][1]) <= max(A[0][1], A[1][1])

うーん、要素を追うだけでも大変ですね。この方向での拡張はあまり得策ではなさそうです。


射影を用いるもう一つの利点として、実装を反復処理に置き換えることが容易であることが挙げられると思います。ここで、多次元にも対応しうる実装に書き換えてみましょう。入れ子になっているzip()が少々難解かもしれません。次回のエントリにて解説したいと思っています。

def intersect(A, B):
    for a, b in zip(zip(*A), zip(*B)):
        if min(a) <= max(b) and min(b) <= max(a):
            pass
        else:
            return False
    return True

うーん、if文の見通しが少々悪いですね。条件の真偽を反転してみます。

def intersect(A, B):
    for a, b in zip(zip(*A), zip(*B)):
        if not (min(a) <= max(b) and min(b) <= max(a)):
            return False
    return True

随分とよくなりました。


ここで、if文の条件を再考してみましょう。実装ではnot演算子により真偽を反転しているため、条件にも不定を付けたところから始めます。

ド・モルガンの法則を利用して、中括弧を外してみます。

否定を伴った不等式も書き換えてしまい、否定記号を消してしまいましょう。

すっきりしました。では、実装に反映してみます。

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


さて、ではこの条件について考えてみましょう。この条件が真である場合、交差判定が失敗することを意味します。

元々の条件よりも複雑になっているのではないか? と思われるかもしれませんが、可視するとそのシンプルさがより明らかとなります。

線分が交差していることを判定するのに比べ、線分が交差していないことをより簡潔かつ明瞭に判定しているように思います。私がこちらの条件のほうがより違和感なく理解することが出来るのもそれが要因ではないかな、と思っています。

まとめ

さて、今回は射影を用いた矩形の交差判定について考えました。次回は今回の実装に用いた、zip()の入れ子に関して補説をしたいと思っています。

Real-Time Rendering, Third Edition

Real-Time Rendering, Third Edition