アルゴリズムクイックリファレンス 第2版

344

■

10

章 空間木構造

たくさんの正方形がウィンドウ内で動き、前後に跳ね返っている中で衝

突を見つける。互いに交差した正方形は赤で示される。

図10-14　四分木を使った衝突検出

10.7.1

 入出力

入力は平面上の

2

次元点集合

P

、そこから

四分木

を構築する。

性能最適化のために、

範囲クエリ

は、

四分木

の節点を返す。これは、ターゲット

の長方形が完全にある部分木を含むときには、その部分木全体を返すことができる

ことを意味する。衝突検出の結果は、ターゲットの点と交差する存在する点の集合

となる。

10.7.2

 解

四分木

の

Pyhon

実装の基本は、例10-4に示す

QuadTree

と

QuadNode

の構造体であ

る。ヘルパーメソッド

smaller2k

と

larger2k

は、最初の領域の辺の長さが

2

のべき

乗となることを保証する。クラス

Region

は、長方形領域を表す。

例

10-4

 四分木

QuadNode

実装

class Region:

def __init__(self, xmin, ymin, xmax, ymax):

"""

領域を

2

点

(xmin, ymin) (xmax, ymax)

から作る。これらが領域の左下および

右上でない場合は適宜調整する。

"""

10.7

 四分木

■

345

self.x_min ...