uniform grid · spatial hash

均匀网格与空间哈希

最省事的二维索引不建树：把平面切成等大的正方形格子，每个点按坐标算出自己在哪一格，塞进那一格的桶里。查询一个矩形时，算出它覆盖了哪些格子，只扫这些桶。

这个结构没有平衡、没有分裂、没有递归，实现不到二十行，却是游戏引擎里最常见的空间索引。它的全部工程内容集中在一个参数上：格子边长该取多少。

1 · 桶号即坐标

网格与哈希表的血缘关系是字面意义上的：格子号就是散列值，只不过这个「散列函数」刻意保留了空间邻近性。

定义 1.1（uniform grid） 给定区域 $[x_0, x_1] \times [y_0, y_1]$ 与格子边长 $c$ ，点 $p$ 所属的格子坐标为 $\left(\lfloor (p_x - x_0)/c \rfloor,\ \lfloor (p_y - y_0)/c \rfloor\right)$ 。桶按行优先展平成一个长度 $\lceil W/c \rceil \cdot \lceil H/c \rceil$ 的数组。

定义 1.2（spatial hash） 不预先分配整个桶数组，而是把格子坐标当 key 送进一张哈希表。区域无界或极稀疏时省内存，代价是每次定位多一次散列与一次可能的 cache miss。

定位是两次减法、两次除法、两次取整，没有比较、没有指针追逐、没有数据依赖。这一点比渐近复杂度重要：它意味着定位可以向量化，也意味着多线程写入不同格子时不需要任何协调，因为格子的位置由坐标算出，与其他点插了什么无关。

范围查询同样直接：查询矩形的四个角落在哪几行哪几列，中间的格子全要扫。

图 1-1 · 均匀网格上的范围查询与最近邻查询。可改格子边长、切换查询类型并拖动查询中心，读数给出扫过的格子数与点级判定次数。

2 · 格子边长与查询尺度的匹配

格子边长决定两项开销的分配：格子越小，每个桶里的点越少（点级判定省），但覆盖同一个查询矩形要扫的格子越多（遍历贵）。

512 见方的场地、2000 个均匀随机点、200 次 60 见方的窗口查询，实测：

格子边长	格子总数	空桶占比	最挤一桶	扫过格子	点级判定
8	4096	61.67%	5	72.67	34.87
16	1024	15.23%	11	22.61	43.88
32	256	0%	21	8.04	62.13
64	64	0%	49	3.69	115.20
128	16	0%	160	1.92	237.61

原先的猜想是「格子越小越好，因为判定次数单调下降」。表里前两列否掉了它：边长从 32 缩到 8，点级判定确实从 62.13 降到 34.87，可扫过的格子数从 8.04 涨到 72.67。格子数已经超过了判定次数，此时主要开销变成了对空桶的遍历，而 61.67% 的桶是空的。

kNN 那一侧的匹配关系更干净。网格上的最近邻查询走同心方环逐圈外扫，圈数直接由「第 $k$ 近的点有多远」决定。同一点集上 $k = 5$ 的平均查询半径实测 12.89，而把两项开销相加后最省的格子边长是 16：

格子边长	扫过格子	距离计算	合计
4	55.64	7.67	63.30
8	20.96	10.48	31.44
12	12.77	13.61	26.37
16	8.45	17.07	25.51
24	7.38	25.89	33.27
32	6.00	50.38	56.38

最优点落在查询半径的同一量级上，而不是某个绝对值。这给出了调参的实际口径：先估出典型查询的尺度（ $k$ 近邻的期望距离约为 $\sqrt{k / (\pi \rho)}$ ， $\rho$ 是点密度），再把格子边长取到同一量级。 $k$ 从 1 变到 20 时这个半径从 4.76 涨到 33.75，跨了七倍。「一个网格伺候所有查询」在 $k$ 变化大的场景下必然有一头吃亏。

警示 · 方环外扫的终止条件容易写错。第 $r$ 圈上的格子离查询点至少 $(r-1)c$ ，不是 $rc$ ——查询点可以落在自己格子的任意位置，包括紧贴边界。少减这个 1 会漏点，而且只在查询点贴近格子边界时漏，随机点集上撞见的概率极低。本系列的实现为它单独留了一条测试（spatial.test.ts 里「查询点贴着格子边界时不漏点」），用三个手工构造的坐标把边界情形钉死，而不是指望随机测试兜住。

3 · 倾斜分布下的空桶与热桶

§2 的数字全部来自均匀随机点。真实数据几乎从不均匀：城市里的店铺、地图上的路网、游戏里的单位，都是一团一团的。

同一批 2000 个点改成 5 个高斯团簇，边长 32 的网格上：47.27% 的桶是空的，最挤的一桶装了 70 个点，而非空桶的平均装载只有 14.81。空桶与热桶同时出现，且不是可以靠调参消掉的——把边长缩到 16，最挤一桶降到 21，空桶占比却涨到 62.50%。

图 3-1 · 均匀分布与团簇分布在同一格子边长下的桶装载。格子按装载深浅着色，右侧柱状图是装载直方图。可切换分布与格子边长，观察空桶占比与最挤一桶如何同时恶化。

这是均匀网格的结构性缺陷，成因在一维索引答不了的问题 §4 已经点出：格线的位置只由坐标系决定，与数据分布无关。数据密的地方格子不会自动变密，稀的地方也不会变疏。

值得注意的是它在查询上的表现并不像装载分布那么难看：团簇分布下 60 见方窗口的点级判定从均匀分布的 62.13 涨到 78.85，只涨了 27%。原因是查询窗也落在同一个分布上：查询打在稀疏区时热桶根本碰不到。所以「装载不均」这件事对吞吐的伤害，取决于查询分布与数据分布有多相关，不能只看直方图。

4 · 与 broad phase 的分工

碰撞检测的 broad phase 要解决的是另一个问题：不是「这个矩形里有哪些对象」，而是「哪些对象两两可能相交」。

均匀网格能干这活：每个对象登记进它覆盖的所有格子，然后逐格取出桶内的对象两两配对。代价是跨格对象要重复登记，且同一对可能在多个格子里被枚举出来，需要去重。另一条路是把二维问题投影回一维——按一个坐标轴排序后扫描，见扫描与剪枝。那条路不建任何结构，只需要一次排序，而且在对象缓慢移动时可以用插入排序增量维护。

两条路的判据是对象的尺寸方差。网格要求格子边长与对象尺寸匹配，一个特大对象会同时登记进上百个格子；排序扫描对尺寸不敏感，但它在某一维上的投影重叠严重时（比如全部对象挤在一条水平带里）退化成 $O(n^2)$ 。

5 · 参考文献

Teschner, M., Heidelberger, B., Müller, M., Pomerantes, D., & Gross, M. H. (2003). Optimized spatial hashing for collision detection of deformable objects. Proceedings of Vision, Modeling, Visualization, 47–54.
Ericson, C. (2004). Real-Time Collision Detection (Ch. 7: Spatial Partitioning). Morgan Kaufmann.
Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures (§1.1). Morgan Kaufmann.