十万个点批量定位区县太慢？给 GeoJSON 加一层 R-tree 空间索引
--- title: 十万个点批量定位区县太慢？给 GeoJSON 加一层 R-tree 空间索引 ---
判断一个经纬度点落在哪个区县，标准做法是 point-in-polygon（点在多边形内）判定。单次查询没有任何问题，麻烦出在批量：把十万条订单坐标匹配到区县时，朴素写法会慢到不可接受，因为每个点都要对全国 2800 多个区县面逐一做射线法判定，总计算量是点数 × 面数 × 平均顶点数。用 R-tree 空间索引能把这类批量查询加速两个数量级。代码全部基于 Node.js 生态的开源库，拿去就能跑。
为什么暴力遍历慢
射线法（ray casting）判定点是否在多边形内，时间复杂度与多边形顶点数成正比。全国区县级 GeoJSON 即使做过Douglas-Peucker 顶点抽稀，单个区县面平均也有数百个顶点，海岸线复杂的区县能到数千。
暴力遍历的总开销：
100000 个点 × 2800 个面 × 平均 500 顶点 = 1.4 × 10^11 次基础运算这个量级在单线程 JavaScript 里要跑几十分钟。仔细想想，绝大多数"点 × 面"配对是纯浪费：一个位于广州的点，根本没必要去和黑龙江的任何区县做精确判定。空间索引干的就是这件事，先用极低成本排除掉不可能命中的面。
R-tree 的核心思路：先粗筛，再精判
R-tree 把每个多边形的外接矩形（bbox，即最小外包框）组织成一棵平衡树，树的每个中间节点是子节点矩形的并集。查询一个点时，从根节点往下走，只进入包含该点的矩形分支，其余整个子树直接跳过。单次查询复杂度从 O(N) 降到 O(log N)。
粗筛返回的是"bbox 包含该点"的候选面，通常只有 1 到 3 个（相邻区县的 bbox 会有少量重叠）。再对这几个候选做精确的 point-in-polygon 判定即可。两阶段流程：
1. 粗筛：R-tree 查询，代价约等于几次矩形比较； 2. 精判：仅对 1～3 个候选面做射线法。
计算量直接从"×2800 个面"缩成"×2 个面左右"。
实战代码：rbush + Turf.js
用到三个库：rbush（R-tree 实现，Leaflet 作者 Vladimir Agafonkin 出品）、@turf/bbox（算外接矩形）、@turf/boolean-point-in-polygon（精确判定）。
npm install rbush @turf/bbox @turf/boolean-point-in-polygon建索引与查询的完整代码：
import { readFileSync } from 'node:fs';
import RBush from 'rbush';
import bbox from '@turf/bbox';
import booleanPointInPolygon from '@turf/boolean-point-in-polygon';
// 1. 读入全国区县 GeoJSON
const fc = JSON.parse(readFileSync('quxian.geojson', 'utf8'));
const features = fc.features;
// 2. 为每个面计算 bbox，批量装入 R-tree
const tree = new RBush();
tree.load(
features.map((f, i) => {
const [minX, minY, maxX, maxY] = bbox(f);
return { minX, minY, maxX, maxY, i };
})
);
// 3. 查询函数：先粗筛后精判
function locate(lng, lat) {
const hits = tree.search({ minX: lng, minY: lat, maxX: lng, maxY: lat });
for (const h of hits) {
if (booleanPointInPolygon([lng, lat], features[h.i])) {
return features[h.i].properties; // 含 name、adcode 等字段
}
}
return null; // 不在任何区县内（如海上）
}
// 4. 测试：天安门坐标应返回北京市东城区（adcode 110101）
console.log(locate(116.397428, 39.90923));这里有两个细节。tree.load() 批量装载用的是 OMT（Overlap Minimizing Top-down）批量构建算法，比逐条 insert() 快得多且树结构更优，一次性建索引务必用 load。另外，索引条目里只存下标 i 而不存整个 feature，避免把几何数据复制一份进树里，内存更省。
三种方案对比
| 方案 | 预处理 | 单点查询 | 支持动态增删 | 额外内存 |
|---|---|---|---|---|
| 暴力遍历 | 无 | O(N)，全量精判 | — | 无 |
| rbush | 一次 load 建树 | O(log N) 粗筛 + 1～3 次精判 | 支持 insert/remove | 每条目一个 JS 对象 |
| flatbush | 一次构建，不可变 | O(log N)，常数更小 | 不支持 | 单块 Float64Array，最省 |
如果面数据固定不变（行政区划边界正是如此），flatbush 是更极致的选择：它把整棵树平铺进一块连续的 TypedArray，没有对象开销，还能把序列化后的索引直接存盘或传给 Worker 线程，省掉重建。需要动态增删要素的场景（比如编辑器）再用 rbush。
顺带一提，这套"bbox 粗筛 + 精判"的思路并非 JavaScript 独有：PostGIS 的 GiST 索引、DuckDB spatial 扩展的 RTREE 索引，底层都是同一套逻辑，只是由数据库引擎代劳了。
一个容易踩的坑：MultiPolygon 的 bbox 空洞
不少沿海区县是 MultiPolygon（陆地 + 岛屿），它的整体 bbox 会把陆地与岛屿之间的大片海域也框进去。落在这片海域的点会通过粗筛、但精判失败，属于正常现象。所以精判这一步绝不能省，不能拿"bbox 命中"当最终结果。如果这类无效候选特别多，可以把 MultiPolygon 拆成多个 Polygon 分别建索引条目，粗筛精度会明显提高，代价是索引条目变多。
另一个前提是坐标系必须一致：点坐标和面数据要同为 WGS84 或同为 GCJ-02，混用会产生数百米偏移，导致边界附近的点匹配到错误的区县。
数据从哪来
全国省、市、区县三级边界 GeoJSON 可以在 GeoJSON 中国按省、市逐级浏览下载，属性里带 name 与 adcode 字段，可直接套用本文代码。如果文件太大读不进内存，先按NDJSON 流式处理的办法切出需要的子集，或参考 Shapefile 转 GeoJSON 的 ETL 链路自行裁剪属性字段，再建索引不迟。
批量匹配十万个点，建索引大约一两秒，之后每个点的查询是微秒级。三十行代码，换来两个数量级的加速。