幾何與區間：概覽
| , 1 minutes reading.
幾何與區間：空間的架構
維度的詛咒
給數字排序很容易。5 比 3 大嗎？是的。 但給空間排序很難。(5, 3) 比 (4, 8) 大嗎？這取決於妳怎麼看。
當數據擁有多個維度（經度/緯度、開始時間/結束時間、X/Y/Z）時，簡單的列表就不夠用了。如果妳想找到「最近的加油站」或者「所有與下午 2 點重疊的會議」，妳不能簡單地掃描一個有序陣列。
本章的主題是 空間索引 (Spatial Indexing)。這是一門將空間（和時間）劃分為可管理層級的藝術，讓我們能以有限的速度查詢無限的平面。
分區的策略
在本章中，我們將從一維的線邁向 N 維的世界：
| 概念 | 靈魂 / 隱喻 | 代表演算法 | 最佳應用場景 |
|---|---|---|---|
| 時間管理 | 日程調度員 在無數重疊的事件中檢測衝突。 | 區間樹 (Interval Tree) | 日曆 尋找空閒時間段。 |
| 縮放 | 變焦鏡頭 遞迴地將 2D 地圖分為 4 個更小的象限。 | 四叉樹 (Quadtree) | 遊戲物理 碰撞檢測與圖像壓縮。 |
| 切割 | 維度切割者 交替切割 X 軸和 Y 軸來組織點集。 | K-D 樹 | 最近鄰搜尋 「找到離地球最近的 5 顆恆星。」 |
| 打包 | 裝箱工 將附近的物體分組成邊界框。 | R 樹 (R-Tree) | 地圖 (GIS) 「找出當前地圖視圖內的所有餐廳。」 |
空間的三大法則
- 層級 (Hierarchy)： 為了高效搜尋空間，妳必須將空曠的區域聚合在一起。如果一個大盒子是空的，妳就沒必要往裡看。
- 重疊 (Overlap)： 與數字排序不同，空間物體可以重疊。一個健壯的演算法必須能處理「同時處於兩個地方」的模糊性。
- 詛咒 (The Curse)： 隨著維度增加，距離變得毫無意義。在 1000 維空間中，任何東西離其他東西都很「遠」。標準的空間樹在這裡會失效（需要近似演算法）。
小結
在本章中，我們將看到電腦圖形學、資料庫和 GPS 系統如何解決「在哪裡」的問題。我們將明白，組織空間與整理雜亂的衣櫃驚人地相似：把東西放進盒子裡，再把盒子放進更大的盒子裡。
讓我們從最簡單的維度開始：時間（一維區間）。