Treating Vectors and Matrices in Python

Python

先日のエントリでは射影を用いた矩形の交差判定について記載しました。その際の実装は以下のようなものでした。

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

実装にはベクトルおよび行列をPythonで扱う技法を用いています。そのため、今回のエントリではまずそちらに関して簡単に記載し、その後に先日の実装の補説をしたいと思います。


さて、以下のような三次元のベクトルを考えてみましょう。

ベクトルをPythonで扱うには、タプルもしくはリストを使用する方法が挙げられます。

>>> a = (a1, a2, a3)

ベクトルの第n要素にアクセスするには、タプルもしくはリストの第n-1要素にアクセスします。

>>> a1 = a[1-1]


同様に行列についても考えてみましょう。例えば、以下のような2行3列の行列を考えてみます。

行列をPythonで扱う方法の一つとして、タプルもしくはリストを入れ子にして行列の要素を格納する方法が挙げられるかと思います。

>>> A = ((a11, a12, a13),
...      (a21, a22, a23),
...     )

行列Aのi行目の成分だけを並べたベクトルをそれぞれa1、a2とすれば、行列は以下のようにも表現出来ます。これは、入れ子になったタプルもしくはリストが行列を表現するのに適していることをよりよく表していると言えるでしょう。

また、上述のコードを以下のように記述すると、相関が分かりやすいかもしれません。

>>> a1 = (a11, a12, a13)
>>> a2 = (a21, a22, a23)
>>> A = (a1,
...      a2,
...     )

行列の第nベクトルにアクセスするには、タプルもしくはリストの第n-1要素にアクセスします。

>>> a1 = A[n-1]
>>> a1
(a11, a12, a13)

これを応用し、行列のm行n列の要素にアクセスするには、第m行ベクトルの第n-1要素にアクセスします。

>>> a21 = A[2-1][1-1]

さて、駆け足ではありますが、以上がベクトルと行列をPythonで扱う技法に関しての解説です。


ここまでを元に、先日のエントリにて解説した矩形の交差判定を考えてみます。引数として、二つの矩形AとBの左下、右上もしくは左上、右下の点の対を与えます。

矩形の対角を成す二点をaおよびbとしましょう。これを二つのベクトルとして表してみます。

関数にはAとBの二つの矩形を与えるのでした。これを示すために、矩形を表す文字を点の右上に付ける約束にしておきましょう。

ここまでを可視すると以下のようになります。今回のエントリでの作図では、矩形の左下と右上の点をそれぞれa、bとしていますが、実際には対角を成す任意の2点の組み合わせとなります。

さて、矩形はa、bの二点で与えることにしたのでした。それぞれの点を行ベクトルと捉えれば、矩形は以下のような行列として表現することが出来ます。

試しに関数を呼び出す側のコードを記述してみます。確かに引数は入れ子になったタプルもしくはリストとなっています。エントリの前半で解説した行列のデータ構造と同じですね。

A = ((axA, ayA),
     (bxA, byA),
     )
B = ((axB, ayB),
     (bxB, byB),
     )
intersect(A, B)


さて、では関数の内側のzip()について考えてみましょう。

zip(*A)

結果から言えば、内側のzip()では行列の転置を行っています。引数でのアスタリスクは続くタプルもしくはリストの要素を引数として展開するため、行列を行ベクトルに分けるような働きをします。

Python3.0からのzip()は、与えられたそれぞれのイテレータから一つずつ要素を取り、タプルとして生成するジェネレータとして実装されています。そのため、まず各行ベクトルの第1要素をその要素としたタプルを生成します。ベクトルで表すと以下となります。

次に、各行ベクトルの第2要素をその要素としたタプルを生成します。

zip()が順次生成する各々のタプルを行ベクトルと捉えれば、zip()の結果も行列を成すと言えるでしょう。

zip()によって得られた行列は、行列Aを転置したものと等しくなります。

これを、矩形A、Bそれぞれの行列に対して行っていますので、内側のzip()群はA、Bそれぞれの転置行列を生成していることになります。


外側のzip()では、内側のzip()にて生成された矩形AとBの転置行列のそれぞれの行ベクトルを順次取得し、合成します。このzip()が生成する各要素も行列を成します。この場合、転置した行列の行数は2ですので、2つの行列群が得られることになります。

行列群を観察してみると、それぞれの行列は矩形のそれぞれの次元の要素のみで構成されていることが分かります。言い換えれば、各軸に対する射影を用いた線分の構成要素をまとめて得ているのです。


for文ではこれらの行列の行ベクトルを変数aおよびbに代入し、線分の交差判定を行います。例えば、一回目の反復では以下のベクトル群を得ます。

これを可視すると以下のようになります。

入れ子にしたzip()により、矩形群をx軸に射影した線分を取得することが出来ました。同様に、二回目の反復では以下のベクトル群を得ることが出来ます。このベクトル群は、矩形群をy軸に射影した線分です。

まとめ

今回のエントリではベクトルと行列をPythonで扱う技法を簡単に解説し、先日のエントリで紹介した実装の補説を行いました。本エントリにて、矩形の交差判定に関するエントリは一先ず揃ったかな、と思います。以下は関連するエントリ群です。


軸に平行な二つの矩形の交差判定という実に簡単明瞭に見える問題ですが、考慮すべきことは多く、Pythonでの実装技法に焦点を当てたエントリも含めてなかなかのボリュームになってしまいました。

やはり計算幾何は奥深く、考えるのが楽しい分野ですね。

Real-Time Rendering, Third Edition

Real-Time Rendering, Third Edition