一种高效的最近点计算算法可计算单表和多表

lanhantable

解决的问题
通信规划中经常要算"哪个基站离我最近"、“这批站点周围有哪些别的站点”。数据量上来以后，逐条遍历算距离会很慢。

工具做了两个标签页：

最近站点1（单表）：同一张表里，每行找最近的 N 个点
最近站点2（双表）：一张表的每个点，去另一张表找最近的 N 个点
下面说算法怎么做的，以及为什么这样做。

算法流程（两个标签页共用一套逻辑）
原始经纬度
    │
    ▼
Equirectangular 投影 → 平面坐标（米）
    │
    ▼
KD-Tree 建索引
    │
    ▼
KNN 搜索（取 N×3 个候选，最少 10 个）
    │
    ▼
Haversine 公式精算 → 按真实距离排序 → 取前 N 个
    │
    ▼
输出到剪贴板

UTM 要分带，跨带的数据会出问题。中国横跨 UTM 49-53 五个带，通信数据覆盖多个省份是常事，用 UTM 得拆开来算，麻烦。
Equirectangular 不分区，整个数据集用同一个参考纬度投影，没有带边界的问题。投影后的平面坐标虽然本身有变形（高纬度区东西方向被拉长），但在 KD-Tree 里只用来"筛候选"，不是最终结果，所以变形不影响精度。
参考纬度取所有点的平均纬度，这样投影变形在数据集范围内整体最小。

KD-Tree + Haversine 两级筛选
只用 KD-Tree 在投影空间算欧氏距离，在地理坐标系里不够准（投影变形）。只算 Haversine，每两个点都算一遍球面距离，一万个点就是五千万次计算，跑不动。
做法是先用 KD-Tree 筛出 N×3 个候选（最少 10 个），然后用 Haversine 精算这些候选的真实球面距离，按真实距离排序取前 N 个。
N×3 这个倍数是经验值。试下来 3 倍 + 保底 10 个，在绝大多数场景下能保证 KD-Tree 投影空间里的前几名和真实球面距离的前几名一致。

双表的差异
双表比单表简单一些：
单表：要排除自己（j == i 跳过），因为自己离自己距离 0
双表：不用排除，直接在表 2 的 KD-Tree 里查就行，查出来的都是另一张表的点
参考纬度取两个表所有点的平均值，保证投影一致性
双表场景很常见：拿现网站址表去匹配规划站点，或者两个不同时期的数据找对应关系。

和暴力遍历的对比
下面是用真实数据跑的时间对比。测试机配置：i7-12700H，Release 编译。

单表（10 万个点，各找最近 1 个）
算法：
暴力双层循环（O(N²)）        耗时~85 秒
KD-Tree（本工具）        ~1.8 秒
数据量越大，提速越明显。暴力法是 O(N²) 增长，KD-Tree 接近 O(N log N)。

KD-Tree 建树的额外开销约 0.2 秒（十万点），平摊到每次查询可以忽略。

和几种常见做法的比较
方法 1：SQLite Spatialite / PostGIS
数据库空间索引（R-Tree）理论上也能做最近邻查询。但实际用起来的问题：

数据要先导入数据库，查完再导回表格，多两步操作
通信工参表格式五花八门，每次都要调导入配置
插件的数据源就是剪贴板，用户从 WPS/Excel 复制，算完粘贴回去，不需要管数据库
本工具直接从剪贴板读，算完写回剪贴板，省掉导入导出。

方法 2：Python (shapely + scipy.spatial)
Python 生态有 scipy.spatial.KDTree 和 shapely，算法能力差不多。

但插件的用户是通信工程师，不是程序员。装 Python 环境、装包、写脚本，大部分人不会去折腾。插件装在 WPS/Excel 里，点一下按钮就出结果。

方法 3：H3  六边形网格索引
H3 可以把经纬度映射到六边形，通过网格 ID 快速找相邻格子里的点。工具里的覆盖分析标签页确实用了 H3，但 H3 不适合做精确的 KNN：

网格边界附近的点容易漏掉，需要查周边多圈
精度受网格层级限制，低层级不够细，高层级网格数爆炸
找最近 N 个点不如 KD-Tree 直接
H3 更适合密度统计、热力图这类需要聚合的场景。

精度
KD-Tree 筛出来的 N×3 个候选，经 Haversine 精算后取前 N 个，精度和纯 Haversine 暴力算完全一致（都基于球面模型）。

两个数据源在 100 公里范围内测试（约 1° 跨度），对比纯 Haversine 暴力计算结果，最近点匹配完全一致。到 500 公里范围（约 5° 跨度），匹配一致率仍大于 99.9%，极少出现因 Equirectangular 投影变形导致筛漏的情况，且漏掉的点距离排在第 N+1 位，差异可以忽略。

表格工具
获取