Quadtreeとは何ですか？

クアッドツリーは、4のべき乗に基づくツリー状の構造であり、データベース内のファイルを整理するために使用されます。 各親ノードまたは開始ノードには4つの子ノードがあり、各子には一定量のデータが保持されます。 データ制限が境界を越えた場合、4つの子がそのノードから作成されます。 2つの主要なクアッドツリー構造があります。リージョンツリーとポイントツリーで、それぞれデザインがわずかに異なります。 クワッドツリーはデータベースで最もよく使用されますが、2D画像のピクセルは常に4つの部分に分割できるため、2次元（2D）画像のピクセルを見つけるためにも使用できます。

すべてのツリー状の構造は、親、またはブランチ、ノード、および子、またはリーフのノードで作成されます。 親は開始点であり、広範なカテゴリベースのデータが含まれていますが、子はファイルとドキュメントを保持しています。 クアッドツリーでは、すべての親に4つの子が必要です。 4つの子が必要ですが、すべての子にデータを含める必要はありません。 なしのノードはヌルノードと呼ばれます。 多くの場合、これらのヌルノードは停滞したままで、データを待ちます。

クワッドツリーの各子ノードにはデータ制限があります。 この制限は通常、データベース全体のサイズによって定義されます。 制限を超えてプッシュする情報が非常に多い場合、子ノードは本質的に出産することで親ノードになり、余分なデータをすべて使用する4つの子ノードを作成します。 通常、この作成から1つまたは2つのヌルノードがありますが、これはノード内のデータ量に完全に依存します。

2つの主要なクアッドツリーがあります：リージョンとポイント。 リージョンクアッドツリーは、2Dリージョン全体を4の累乗（4、8、または16パートなど）に基づいてパーツに分解するために使用され、表現によく使用されます。 この構造は、画像またはデータフィールドグラフに最適です。 ポイントバージョンはバイナリツリーのようなもので、順序付けされたポイントで使用するのが最適です。 ノードが散在しているリージョンバージョンとは異なり、このバリアントは真のツリーでもあります。これは、すべてのノードが発生する中心点があるためです。

クアッドツリーの最も一般的な使用法は、データベースを分離して整理することですが、これが唯一の使用法ではありません。 画像内の特定のピクセルを見つけるために作成されたアルゴリズムは、一般的に四分木を使用します。これは、画像内の各ピクセルを4つの等しい部分に分割できるためです。 これにより、四分木はピクセルの検索に特に適しています。