把1.4万座山峰落到村界：网格索引快了102倍

技术专栏 · 数据处理 · 2026-10-15

重庆最高峰阴条岭，海拔 2,797 米，落在巫溪县马塘村的地界里。这个结论不是查来的，是算出来的：把本站一键地形图的地名资产——14,246 座山峰的坐标——逐一问过重庆市包的 10,847 个村级面，谁包含它，它就归谁。这一问一答叫空间连接，本文把两种做法都跑了一遍：暴力法 508 毫秒，网格索引 5 毫秒，快 102 倍，判定结果完全一致。

点在面里吗：射线法与一个静默的坑

判断点在面内用射线法：从点引一条射线，数它与面边界的交点，奇数在内、偶数在外。实现只有几行，但第一版跑完，14,246 个点命中 0 个——没有报错，没有异常，就是全空。排查半小时，根因在数据预处理：重庆市包的要素全部是 MultiPolygon，坐标是「面→环→点」三层，第一版按「环→点」两层去遍历，拿到的坐标全是数组而不是数字，包围盒算出来是 NaN，后续所有比较静默失败。修法是按类型摊平：

const ringsOf = f => {
  const c = f.geometry.coordinates;
  return f.geometry.type === 'Polygon' ? c          // [环, ...]
       : c.flatMap(p => p);                         // MultiPolygon：摊平成 [环, ...]
};
// 射线法：奇数在内，偶数在外
function pip(rings, x, y) {
  let inside = false;
  for (const r of rings) {
    for (let i = 0, j = r.length - 1; i < r.length; j = i++) {
      const [xi, yi] = r[i], [xj, yj] = r[j];
      if ((yi > y) !== (yj > y) && x < ((xj - xi) * (y - yi)) / (yj - yi) + xi) inside = !inside;
    }
  }
  return inside;
}

摊平之后立刻命中 52 处——落入重庆市范围的 77 座山峰里，52 座找到了自己的村。这个坑的阴险之处在于不报错：MultiPolygon 在全国村界数据里是常态（有飞地的村、有群岛属性的区），任何点在面内的脚本都该先过这一关。

慢在哪：暴力法的 508 毫秒花给了谁

基线做法是逐面包围盒预判加射线法——这已经是朴素方案里带优化的写法。14,246 个点对 10,847 个面，包围盒判断要跑约 1.5 亿次，实测 508 毫秒。负载轻的时候（重庆范围内的 77 个真实山峰）它只要 10 毫秒，完全够用；点数上万之后，每多一个点都要把全部面重新问一遍，成本线性叠加，这就是暴力法的天花板。

网格索引：先问格子，再问面

思路是把地图划成 128×96 的均匀网格，每个面把自己的包围盒登记进它压到的所有格子；查询时点只落在一个格子里，先取出登记在该格的候选面，再对候选面做射线法。重庆村界面小而密，实测平均每个点只有 0.1 个候选面——绝大多数格子是空的，查个空表就返回了：

const GX = 128, GY = 96, grid = new Map();
for (let i = 0; i < polys.length; i++) {          // 建索引：登记包围盒
  const [cx0, cy0] = cellOf(Math.max(p.x0, lonMin), Math.max(p.y0, latMin));
  const [cx1, cy1] = cellOf(Math.min(p.x1, lonMax), Math.min(p.y1, latMax));
  for (let cx = cx0; cx <= cx1; cx++) for (let cy = cy0; cy <= cy1; cy++) {
    const k = cx + ',' + cy;
    (grid.get(k) || grid.set(k, []).get(k)).push(i);
  }
}
// 查询：点所在格子 → 候选面 → 射线法
const cand = grid.get(cellOf(x, y).join(',')) || [];
for (const i of cand) if (pip(polys[i].rings, x, y)) return i;

两种算法对全部 14,246 个点的判定逐一比对，结果完全一致——索引只改变查找路径，不改变几何判定。平均候选面 0.1 个的意思是：绝大多数点所在的格子压根没有面登记，一轮哈希查找就结束了。

连接结果：77 座山峰的落村账

落进重庆市范围的 52 座山峰，区县分布头尾悬殊：合川 17 座（华蓥山余脉）、北碚 7 座（缙云山一带）居前，三峡库区的巫山、巫溪、奉节各有斩获。海拔最高的几座，落村结果个个对得上常识：

没命中的 25 座不是漏算：它们落在包围盒的四个角上，地界属于贵州、四川或湖北，查不到归属是正确行为。看一眼分布图，金佛山在南川与贵州交界处、神女峰正对长江巫峡——落点与地物一一咬合。

规模门槛：什么时候才值得建索引

77 个点的真实负载里，暴力法 10 毫秒、索引 2 毫秒，差出来的 8 毫秒没人感知，为它建索引属于过度设计。判断标准看乘积：点数 × 面数的判断次数，超过一千万次就该建——本文的压力负载是 1.4 万 × 1.1 万 ≈ 1.5 亿次，索引收益 102 倍。网格的构建只要几毫秒且一次构建反复查询，做点位打标、设备落格这类常驻服务时，索引几乎总是划算。面数据本身的质量检查（有无缝隙重叠导致的双重归属）在《边界数据拓扑检查：一段脚本查出缝隙与重叠》里有一套可复现的做法；代码体系见《12位村级代码怎么读：逐段拆解与真数据验证》，要参与连接的村界数据在村界数据 · 按市各页按市取用。

常见问题

怎么判断一个点落在哪个行政村内？

用射线法：从该点向任意方向引一条射线，数它与面边界的交点，奇数在内、偶数在外。批量判断时先做面包围盒预判再跑射线法。本文实测重庆 10,847 个村级面上做 1.4 万点的归属，逐面包围盒加射线法耗时 508 毫秒。

网格索引为什么能快 100 倍？

它把「点对全部面」的判断压缩成「点对几个候选面」：把地图划成 128×96 的均匀网格，每个面的包围盒登记进它压到的格子里；查询时点只落在某一个格子里，与该格内登记的面做判断即可。实测平均每个点只有 0.1 个候选面，14,246 点的查询从 508 毫秒降到 5 毫秒，构建索引本身只花约 5 毫秒。

MultiPolygon 数据直接当 Polygon 用会怎样？

会把「面→环」两层结构当成一层遍历，拿到的坐标全是数组而不是数字，所有数值比较静默失败——本文第一版因此得到 0 命中，且没有任何报错。正确做法是按 geometry.type 分支：Polygon 直接取环列表，MultiPolygon 要把各面的环摊平合并后再做包围盒与射线法。

什么规模才值得建空间索引？

看点数与面数的乘积。77 个点对 10,847 个面，暴力法只要 10 毫秒，索引只省 8 毫秒，不值得；点数上到万级（乘积过亿），本文实测 508 毫秒对 5 毫秒。经验门槛：乘积超过一千万次判断就该建索引，构建成本在毫秒级，一次性付出。

点位落在面外或边界上怎么办？

面片经过拓扑清洗后无缝无重叠，市域内的点必然命中恰一个面；落在市域外的点（本文压力负载 14,246 个点里只有 52 个在重庆市内）查不到归属是正常结果，按未命中处理即可。恰在边界上的点受浮点误差影响可能两边都不认，批量场景建议先给坐标做一致性取整再判断。