區域資料結構

儲存大量幾何物體、查詢周遭幾何物體的資料結構。

物體位置不限，到處遍布，甚至重疊。物體形狀不限，點、直線、曲線、矩形、圓形、三角形、……。物體形狀不需一致。

區域資料結構的功能：

一、找到相交物體。例如輸入一條線段／射線／直線，輸出碰觸的物體們。

簡易方式是枚舉法。窮舉每個物體，一一判斷相交。

進階方式是區域資料結構。事先劃分區域，依照區域儲存物體。只需要檢查直線穿越的區域、區域裡面的物體，不需要檢查所有區域、所有物體。

二、找到相鄰物體。例如輸入一條線段／射線／直線，輸出距離範圍之內的物體們。

事先調整區域大小，盡量符合距離範圍。只需要檢查附近的區域們，不需要檢查更遠的區域們。

這樣的資料結構，目前沒有正式學術名稱。

位置是區域的特例

當輸入一律是點，當物體一律是多邊形（化作一群頂點），那麼可以使用point資料結構的長方形範圍查詢。

uniform grid

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

實作方式是一個二維陣列，對應方格紙。陣列每一格是一個串列，對應每個方格包含的物體。

如果物體跨據多個方格，那麼同時儲存於多個方格。

插入、刪除、搜尋的時間複雜度是O(N)，N為物體數量。然而，串列長度通常遠少於N，這種時間複雜度標記法缺乏意義。

bitree / quadtree / octree

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

以四元樹為例：分割平面為四等分，視情況可以遞迴分割下去，越分越細。物體放在樹葉。

插入、刪除、搜尋的時間複雜度是O(N)，N為物體數量。然而，樹的高度通常遠少於N，這種時間複雜度標記法缺乏意義。確切的時間複雜度難以估計，取決於樹深與分枝數。

UVa 297 806 11941 11948

k-dimensional tree

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

此處的kd-tree，注重每個物體的邊界範圍；原本的kd-tree，注重每個點的位置先後順序。兩者用途不一樣。

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

插入、刪除、搜尋的時間複雜度是O(N)，N為物體數量。然而，樹的高度通常遠少於N，這種時間複雜度標記法缺乏意義。

bounding interval hierarchy / bounding region hierarchy / bounding volume hierarchy

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

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

插入、刪除、搜尋的時間複雜度是O(N)，N為物體數量。然而，樹的高度通常遠少於N，這種時間複雜度標記法缺乏意義。

優點是：不必煩惱物體跨據多區。可以旋轉節點，令樹平衡。

UVa 12312 ICPC 7605

ball tree

長方體改成球。

R-tree

bounding volume hierarchy與B-tree合體。