データ構造のRツリー
-
多次元情報の索引付け
-
ゲームデータの処理
-
地理空間座標を保持する
-
仮想マップの実装
Rツリーの一例は以下のようなものです。
対応するRツリーは次のようになります-
Rツリーのプロパティ
-
Rツリーは、単一のルート、内部、およびリーフノードで構成されています
-
ルートには、特別なドメイン内の最大の領域へのポインターがあります
-
親ノードは、子ノードが親ノードの領域と完全にオーバーラップする子ノードを保持します
-
リーフノードは、MBRに関するデータを現在のオブジェクトに保持します
-
MBR-最小境界領域は、検討中の領域を囲む最小境界ボックスパラメータです
| クワッドツリー | Rツリー |
| タイリングレベルの最適化が必要です | R-Treeは最適化を必要としません |
| 四分木はB木に形成できます | RツリーはBツリーの構造に準拠していません |
| 空間インデックスの作成が高速です | 空間インデックスの作成が遅い |
| 最近傍クエリは遅くなりますが、ウィンドウクエリは速くなります。 | 最近傍クエリは高速ですが、ウィンドウクエリは低速です。 |
-
データ構造のB+ツリー
ここでは、B+ツリーとは何かを確認します。 B +ツリーは、Bツリーの拡張バージョンです。このツリーは、Bツリーのより良い挿入、削除、および検索をサポートします。 Bツリー、キー、およびレコード値は、内部ノードとリーフノードに格納されます。 B +ツリーレコードでは、リーフノードに保存できます。内部ノードはキー値のみを保存します。 B+ツリーのリーフノードもリンクリストのようにリンクされています B+ツリーの例 − これは、検索、挿入、削除などの基本的な操作をサポートします。各ノードで、アイテムが並べ替えられます。位置iの要素には、その前後に子があります。したがって、以前に痛んだ
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ