逆地理落点算法 (Reverse Geocoding Anchor Matching)
逆地理(Reverse Geocoding)指「坐标 → 地点名称」的换算。工程上有两条路线:
- 厂商逆地理:调百度 / 高德的
reverse_geocoding接口,拿回一串行政区划地址。 - 本地 POI 就近匹配:拿自建的 POI 数据集做最近邻检索,直接给出具体场所名。
校园导航这类场景要的是后者——用户问「我在哪」,想听的是「你在图书馆旁边」,
而不是「浙江省宁波市鄞州区钱湖南路8号」。所以这套算法的主干不是调接口,
而是本地就近匹配,匹配不上才回落厂商接口。
但一上手就会撞上一个矛盾,整套设计都在处理它。
核心矛盾:几何最近 ≠ 认知最近
人走在主干道上,几何上最近的那个 POI 经常是噪声点:
- 停车场的出入口角点
- 充电桩
- 公交站牌
- 商业广场里某家没有招牌的奶茶铺
按「谁近用谁」,用户站在校门口会被告知「你在永易充充电站旁边」。
这不是一句能用的指路话。
「最近」是一个几何量,而用户需要的是一个可指路量。这两个量在 POI 数据上不重合。
解法:分层优先最近邻 (Priority-Tiered Nearest Neighbor)
不做「全体比距离」,而是先按可接受度筛集合,再在层内比距离:
第一层:在「大地点集合」里取最近点
距离 ≤ 阈值 → 用它,标记 anchor = true
第二层:大地点全部超出阈值(集合里一个都不够近)
→ 才在全集里取最近点,≤ 阈值就用,标记 anchor = false顺序不能反。 小铺往往比教学楼近得多,写成「谁近用谁」就退化成朴素最近邻了。
这里的「大地点」(Anchor)定义是可指路性(referability):
能被指路时说出口的楼栋、场馆、有招牌的店。判据两层,前者权威:
- 人工覆盖:POI 上带一个
anchor字段,管理端可定死true/false; - 关键词规则:噪声词否决 → 混杂分类落关键词细判 → 其余分类默认是大地点。
人工覆盖的存在是有意的:规则负责覆盖大多数,人工覆盖负责兜住长尾,
且不用改代码、不用等发版。详见 POI 标签混入位置信息污染分类判据 (Location Tags Polluting POI Rule Judgment)。
两条工程约束
1. 降级可以,但降级必须可见
第二层的落点只标记 anchor = false,不拒绝返回。理由:
- 完全拒绝 → 用户站在广场中央会得到「无法定位」,体验更差;
- 返回但标记「这个落点只是凑合」→ 调用方能据此软化话术,或提示「附近没有明显地标,已按最近地点估算」。
静默降级会让下游无法区分「准确落点」和「凑合落点」,这是比降级本身更严重的问题。
这个约束可以推广到任何「主路径失败后走兜底」的设计:兜底结果必须携带「我是兜底」这个信息。
2. 输入坐标系必须显式声明
浏览器 / 手机原生定位给的是 WGS84(GPS 原始值),而国内 POI 数据集和百度地图用的是
BD09(国测局加密偏移后的坐标系)。两者在宁波一带相差 500 米以上——不换算,
最近点会直接找错人(500 米足以跨过好几个 POI 的覆盖范围)。
换算链:
WGS84 ──(国测局加偏算法)──> GCJ02 ──(百度再偏一次)──> BD09
浏览器定位 高德等国内地图 百度地图 / 本数据集关键约束:算法无法从数值上判断一个坐标属于哪套坐标系,必须由调用方声明。
这是一条不能猜的信息——三套坐标系的数值范围完全重叠。
阈值怎么定
| 阈值 | 典型值 | 含义 | 取值理由 |
|---|---|---|---|
| 本地生效半径 | 150 m | 距校内 POI 在此以内才认可本地结果 | 太大 → 吸附到几百米外的建筑,落点失真;太小 → 校园边角频繁掉出本地范围,回落厂商接口既慢又只给地址串。150m 约等于「一个建筑组团」的尺度 |
| 校区识别半径 | 500 m | 距最近校内 POI 在此以内才认定身处该校区 | 需大于 POI 覆盖的最大空隙(否则校区内部有「盲区」认不出校区),同时远小于跨校区间距(否则误判到隔壁校区) |
注意二者用不同判据:校区识别用任意最近点(不分层),落点匹配才用两层。
原因是稀疏校区里最近的可能是某个小铺,按大地点判会导致认不出校区。
这是刻意的不一致,不要顺手「统一」。
筛选放在哪一层:离线还是运行时
上面描述的「两层 + 关键词判据」是运行时形态。但只要满足两个条件,
同一件事可以搬到离线做,把运行时塌缩成一次普通最近邻:
- 判据是确定性的(同样的输入永远给同样的输出,没有随机、没有外部状态);
- 输入数据是静态的(不随运行变化,或变化频率远低于发版频率)。
完整 POI 数据集 (202 条,会随采集变化)
│ 离线筛一次(关键词判据在这里跑)
▼
参照物表 (131 条,烘进产物)
│ 运行时(没有关键词、没有分层,就是最近邻 + 半径)
▼
返回最近的一个换来的:运行时不需要关键词表、不需要分层逻辑、不需要读数据文件——
整个实现塌缩成一个函数,数据可以内嵌。
付出的:
- 数据更新要走「重新筛 → 重新发版」的流程,运行时没有重新筛的能力;
- 人工覆盖(
anchor字段)也从「管理端随时可改」变成「改完要发版」; - 判据的调整历史不再体现在产物里,只在生成脚本里。
判断依据:产物是发给第三方(对方只读不写、数据由我方控制),
离线做显然划算;产物是长期自运维的服务(对方要自己改点、自己调规则),
运行时做更合适,否则每次调规则都要发版。
这个取舍与「物化视图 vs 实时查询」「预编译 vs JIT」是同一类问题:
当规则确定且数据静态时,把规则的执行结果烘进产物,用「更新成本」换「运行成本」。
本项目两种形态都存在:线上服务走运行时(管理端可改点位、可调覆盖),
对外交付的教学示例走离线(数据内嵌,一个函数)。
这个模式的可迁移形态
「分层优先最近邻」不限于逆地理。凡是多个候选都「最近」,但可接受度不同的场景都适用:
| 场景 | 第一层 | 第二层 |
|---|---|---|
| 逆地理落点 | 可指路的大地点 | 任意最近 POI |
| 搜索建议 | 标题命中的条目 | 正文命中的条目 |
| 缓存淘汰 | 已过期且无访问的条目 | 按 LRU 淘汰 |
| 路由匹配 | 精确 / 前缀路由 | 通配路由 |
共同结构:**先按「可接受度」过滤出一个子集,在子集内比较度量;子集为空才放宽到全集,
且放宽这一事实要让调用方看得到。**
这与「加权求和」是两种不同的思路——加权求解的是「综合最优」,分层求解的是
「在满足硬条件的候选里最优」。当某一维是硬性禁用条件(如噪声点根本不可接受)时,
分层比加权正确。
参考实现
三份等价参考实现(Python / Node.js / Java,零依赖,同一组 58 条用例,跨语言逐字段对账通过):
交付包 逆地理算法交付包,含算法说明、教学数据集与 tools/cross-check.mjs。
线上实现:campus-navi-rs 仓库 crates/campus-geo/src/reverse.rs(入口 ReverseService::reverse)
与 crates/campus-core/src/anchor.rs(大地点判据)。
相关概念
- POI 标签混入位置信息污染分类判据 (Location Tags Polluting POI Rule Judgment)
- Haversine 球面距离 (Haversine Distance)(待写)
- 坐标系 WGS84 GCJ02 BD09(待写)
- React 定位副作用引发重复请求 (Geolocation Side Effects Causing Duplicate Requests)——同项目的定位链路,消费方视角
本文归档于个人知识库 · 领域:CS & AI · 模块:04 Project_CS_AI/Algorithms