ポイントクアッドツリー（四分木）とは？2次元データを扱うデータ構造の基本と仕組み

ポイントクアッドツリー（点四分木）の概要

ポイントクアッドツリー（Point Quadtree、点四分木）は、2次元の点データを表現するために二分木（バイナリツリー）を拡張・応用したデータ構造です。すべての四分木（クアッドツリー）に共通する特徴を受け継いでいます。

ポイントクアッドツリーは、順序付けられた2次元データ点同士を比較する処理において非常に効率的で、多くの場合 O(log n) の時間で実行できます。網羅的な解説として取り上げる価値のある構造ですが、汎用的な二分探索ツールとしては、k-d木の方が優れているとされています。

ポイントクアッドツリーの構築方法

ポイントクアッドツリーは、以下の手順で構築されます。

新しい点を挿入する際には、その点が属するセル（領域）を計算し、木に追加します。このとき、新しい点を含むセルは、その点を通る垂直線と水平線によって4つの象限（クアドラント）に分割されます。その結果、各セルは長方形にはなりますが、必ずしも正方形になるとは限りません。

この木では、各ノードが入力された点のうちの1つに対応します。

挿入順序による影響

平面の分割は点の挿入順序によって決まるため、木の高さは挿入順序に敏感に依存します。不適切な順序で挿入すると、ノード数に対して線形の高さを持つ木になってしまうことがあります（この場合、事実上連結リストと同じ状態になります）。

一方、点集合が静的（固定）である場合は、事前処理を行うことで高さがバランスの取れた木を構築できます。

ポイントクアッドツリーのノード構造

ポイントクアッドツリーのノードは、通常の二分木のノードとほぼ同じ構造ですが、大きな違いとして、ポインタが「左」「右」の2つではなく、4つの象限それぞれに対応した4つのポインタを持つ点が挙げられます。また、キーは通常、x座標とy座標の2つの部分に分けて管理されます。

したがって、ノードは次の情報で構成されます。

• 4つのポインタ： quad['NW']、quad['NE']、quad['SW']、quad['SE'] の4種類
• NW＝北西（North West）、NE＝北東（North East）、SW＝南西（South West）、SE＝南東（South East）を意味します
• point（点）： さらに以下の要素から構成されます
• key（キー）： 通常は x・y 座標で表されます
• value（値）： 名前などの付随情報