Region 資料結(jié)構(gòu) :?
Uniform Grid

楔子

請你嘗試發(fā)掘，這一系列的資料結(jié)構(gòu)是為了解決什麼問題呢？

Uniform Grid

嗯，就是方格紙。將整個世界劃分為等寬方格。

實(shí)作方式是一個二維陣列，對應(yīng)方格紙。陣列每一格是一個串列，對應(yīng)每個方格包含的資料。

資料可以是任何東西，例如點(diǎn)、線段、三角形。

如果資料跨據(jù)多個格子，那麼可以同時儲存於多個格子，或者只儲存於其中一個格子。隨你開心。

插入、刪除、搜尋的時間複雜度是 O(N) ， N 為資料數(shù)量；然而，串列長度通常遠(yuǎn)少於 N ，因此這種時間複雜度標(biāo)記法缺乏意義。

Region 資料結(jié)構(gòu) :?
Quadtree

Bitree / Quadtree / Octree / Hextree

二元樹、四元樹、八元樹、十六元樹，分別是一、二、三、四維的版本。

以四元樹為例：分割平面為四等分，視情況可以遞迴分割下去，越分越細(xì)。

資料放在樹葉。資料可以是任何東西，例如點(diǎn)、線段、三角形。

插入、刪除、搜尋的時間複雜度是 O(N) ， N 為資料數(shù)量；然而，樹的高度通常遠(yuǎn)少於 N ，因此這種時間複雜度標(biāo)記法缺乏意義。確切的時間複雜度難以估計(jì)，取決於樹深與分枝數(shù)。

UVa?297?806?11941?11948

Region 資料結(jié)構(gòu) :?
k-Dimensional Tree

k-Dimensional Tree

額外繪製垂直線、水平線來分割區(qū)域。由於概念類似 KD-Tree ，所以大家沒有另起他名，直接沿用舊名。

此處的 KD-Tree ，注重每筆資料的邊界範(fàn)圍；原本的 KD-Tree ，注重每個座標(biāo)點(diǎn)的位置先後順序。兩者用途不一樣。

採 top-down 方式，依照某一個座標(biāo)軸排序所有資料（通常是跨距最廣的那個座標(biāo)軸），將資料等分為左右兩堆，遞迴分割下去。

插入、刪除、搜尋的時間複雜度是 O(N) ， N 為資料數(shù)量；然而，樹的高度通常遠(yuǎn)少於 N ，因此這種時間複雜度標(biāo)記法缺乏意義。

缺點(diǎn)是：資料跨區(qū)時，不知該安置於哪區(qū)。除非資料是點(diǎn)。

Region 資料結(jié)構(gòu) :?
Bounding Volume Hierarchy

Bounding Interval Hierarchy / Bounding Region Hierarchy / Bounding Volume Hierarchy

BIH 、 BRH 、 BVH 分別是一、二、三維的版本。

採 top-down 方式，依照某一個座標(biāo)軸排序所有資料（通常是跨距最廣的那個座標(biāo)軸），將資料等分為左右兩堆，遞迴分割下去。

插入、刪除、搜尋的時間複雜度是 O(N) ， N 為資料數(shù)量；然而，樹的高度通常遠(yuǎn)少於 N ，因此這種時間複雜度標(biāo)記法缺乏意義。

優(yōu)點(diǎn)是：不必?zé)涝摪仓渺赌膮^(qū)。可以旋轉(zhuǎn)節(jié)點(diǎn)，令樹平衡。

UVa?12312

Region 資料結(jié)構(gòu) :?
R-Tree

R-Tree

Bounding Volume Hierarchy 與 B-Tree 合體。

from:?http://www.csie.ntnu.edu.tw/~u91029/Region.html#3

總結(jié)

以上是生活随笔為你收集整理的Uniform Grid Quadtree kd树 Bounding Volume Hierarchy R树 搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。