几何与区间：概览
| , 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 系统如何解决“在哪里”的问题。我们将明白，组织空间与整理杂乱的衣柜惊人地相似：把东西放进盒子里，再把盒子放进更大的盒子里。
让我们从最简单的维度开始：时间（一维区间）。