[筆記] K-D Tree v.s. Quad Tree

在計算幾何中其實很常會出現需要找出在座標平面上的一堆點或線段中位於特定區塊中的點或線段。舉例來說，想找出二維座標平面上找出落在 (0, 0) ~ (10, 10) 這個矩形區域點的所有點，並且對這些點做處理。常用的資料結構有幾個：

• R-Tree (可以衍伸出 R+-Tree, R*-Tree)
• K-D Tree
• Quad Tree
• Bounding volume hierarchy (BVH)

根據要應用的情境各有優缺點，使用前要詳細閱讀說明書 (?


以下資料結構的詳細操作就不多說了，只提簡單的比較

R-Tree

基本上是用來處理矩形的 (所以至少要是二維平面，但可以延伸應用至多維)，允許動態的增減 tree 中儲存的矩形數量。設計的好的話可能有辦法退化到處理點或線段，不過不太建議就是，因為考慮這種狀況會讓條件判斷有點難處理。

K-D Tree

可以退化到只有一維直線上的點，也可以延伸到處理多維。在一維直線上的應用情況其概念跟 binary search tree 超像，只是點是都存在 leaf，而不是像 binary search tree，parent node 也會儲存資料。另一個最大的差異，則是 KD-Tree 沒辦法動態的改變架構，所以比較適合用在資料不會改變，但是會一直做查詢狀況。至於沒辦法動態的改變其最大原因就來自他的資料都是存在 leaf，如果要動態的更新架構會很麻煩的

Quad-Tree

一樣最少是用在二維平面，但也可以延伸至高維。Quad 的來源則是因為他在二維平面時每次分區一群點座標都是把他們分割成四個象限，一個象限用一個 node 來表示，如此反覆的直到 leaf 只保留一定數量以下 (通常是一個) 的點座標。應用範圍好像滿廣的，連影像處理的領域好像都有用到。很常被拿來跟 K-D tree 比較，不過因為 K-D Tree 其概念很像 binary search tree，所以比較常被提到的樣子，但是 Quad-Tree 相較於 K-D Tree 其優點就是能動態的改變架構。不過缺點就是頻繁的改變會讓架構變得太過於零碎 (因為每次都會分成四個象限)，其中一種權衡的方法就是調整 leaf node 最多可以容納幾個點。

BVH

這個好像專門用在處理物件之間的關係 (像是碰撞、遮蔽之類的) 的運算上。概念簡單來說就是把鄰近的幾個物件用一個比較大的物件包起來，如此反覆的一層一層包住就可以變成像是 tree 的架構，方便用來縮減要運算的物件數量。跟前面幾種比起來最大的差異應該就是這個完全沒有說他的物件要是甚麼形狀，不過實際應用如果想要真的減少要運算的物件數量，那每次 "把鄰近物件包成更大的一個物件" 這項操作要盡可能地讓那些大物件不會有相交，這樣才能真的避免不必要的運算。但這也是最大的應用限制就是，這條件其實沒那麼好達成。

這篇也有簡單的描述，可以當作參考