通信人家园
标题:
一种高效的最近点计算算法可计算单表和多表
[查看完整版帖子]
[打印本页]
时间:
2026-7-14 09:41
作者:
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 位，差异可以忽略。
表格工具
获取
2026-7-14 09:39 上传
下载附件
(62.41 KB)
2026-7-14 09:39 上传
下载附件
(69.09 KB)
附件:
04ee0877a4d44b389956eb54e9d49b7a.png
(2026-7-14 09:39, 62.41 KB) / 下载次数 0
https://www.txrjy.com/forum.php?mod=attachment&aid=NzI3ODczfGVlMDE2NmUxfDE3OTE4MjA5Nzd8MHww
附件:
a9f194040116485cb1519bc87df153f3.png
(2026-7-14 09:39, 69.09 KB) / 下载次数 0
https://www.txrjy.com/forum.php?mod=attachment&aid=NzI3ODc0fDg5ZTBlZGNhfDE3OTE4MjA5Nzd8MHww
时间:
2026-7-14 09:55
作者:
txrfangyuan
感谢分享
时间:
2026-7-14 10:09
作者:
lanhantable
python的用法如下双表的（单表的用min_distance_onetable）
import pandas as pd
import tablegis as tg
# 创建两个示例DataFrame
df1 = pd.DataFrame({
'id': [1, 2, 3],
'lon1': [116.404, 116.405, 116.406],
'lat1': [39.915, 39.916, 39.917]
})
df2 = pd.DataFrame({
'id': ['A', 'B', 'C', 'D'],
'lon2': [116.403, 116.407, 116.404, 116.408],
'lat2': [39.914, 39.918, 39.916, 39.919]
})
# 计算最近的1个点
result = tg.min_distance_twotable(df1, df2,lon1='lon1', lat1='lat1', lon2='lon2', lat2='lat2', df2_id='id', n=1)
# 计算最近的2个点
result2 = tg.min_distance_twotable(df1, df2,lon1='lon1', lat1='lat1', lon2='lon2', lat2='lat2', df2_id='id', n=2)
print("\n结果示例（距离单位：米）:")
print(result)
print(result2)
复制代码
通信人家园 (https://www.txrjy.com/)
Powered by C114
附件: 04ee0877a4d44b389956eb54e9d49b7a.png (2026-7-14 09:39, 62.41 KB) / 下载次数 0附件: a9f194040116485cb1519bc87df153f3.png (2026-7-14 09:39, 69.09 KB) / 下载次数 0
感谢分享