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

10.7

 四分木

■

349

class QuadTree:

def collide(self, pt, r):

"""

四分木内で点に衝突するものを返す

"""

if self.root is None:

return None

return self.root.collide(pt, r)

10.7.3

 分析

四分木

は、平面上の点を二分探索木と同様の構造を使って分割する。ここで示し

た実装は、点の集まりが一様分布しているときに効率的な振る舞いをする固定分割

方式を使用している。図10-15のように、点が小さな空間にすべて偏っていること

もある。したがって、探索性能は木のサイズの対数となる。

Python

による

範囲クエ

リ

は個々の点だけでなく、

四分木

の節点全体も返すので効率的である。しかし、

範

囲クエリ

において、返された節点のすべての子孫の値を取り出す時間については、

考慮する必要がある。

図10-15　退化した四分木

10.7.4

 変形

ここに示した四分木構造は、領域四分木である。点四分木は、

2

次元の点を表す。

八分木は、

四分木

を

3

次元に拡張したもので、

4

つではなく

8

つの子（立方体）を持

つ（

Meagher, 1995

）。