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

10.4

 空間木構造

■

323

孫の節点の領域全体を含んでいる。

10.4.2

 四分木

四 分 木

（

quadtree

）は、

2

次元 点 集合

P

に対し て、再 帰的 に全 空間 を 四分 儀

（

quadrant

）に分割する。これは木に似た構造で、内部節点には、

NE

（北東）、

NW

（北西）、

SW

（南西）、

SE

（南東）のラベルの付いた

4

つの子がある。

四分木

には次の

2

つの種類がある。

領域ベース

各ピクセルが

0

か

1

の

2

k

×

2

k

のピクセルによる画像があるとする。

四分

木

の根が画像全体を表す。根の

4

つの子は元の画像の

2

k

-1

×

2

k

-1

の各四分

儀を表す。もし、この四分儀の

1

つが、全部

0

でも全部

1

でもないとする

と、さらに親の

4

分の

1

のサイズの部分領域に分割する。葉は、ピクセ

ルが全部

0

か全部

1

かの正方形領域を表す。図10-3 は、画像ビットマッ

プの例に対する四分木構造を示す。

領域サイズ

8

×

8

4

×

4

2

×

2

1

×

1

図10-3　領域ベース分割を用いた四分木

＊1

＊1 訳注：領域ベース分割を用いた

四分木

のことを、「領域四分木」（region quadtree）と言う。