解决的问题通信规划中经常要算哪个基站离我最近、“这批站点周围有哪些别的站点”。数据量上来以后逐条遍历算距离会很慢。工具做了两个标签页最近站点1单表同一张表里每行找最近的 N 个点最近站点2双表一张表的每个点去另一张表找最近的 N 个点下面说算法怎么做的以及为什么这样做。算法流程两个标签页共用一套逻辑原始经纬度 │ ▼ Equirectangular 投影 → 平面坐标米 │ ▼ KD-Tree 建索引 │ ▼ KNN 搜索取 N×3 个候选最少 10 个 │ ▼ Haversine 公式精算 → 按真实距离排序 → 取前 N 个 │ ▼ 输出到剪贴板几个设计点的意图Equirectangular 投影不用 UTM投影选的是等距圆柱投影Equirectangular公式很简单x lon × 111320 × cos(refLat) y lat × 111320UTM 要分带跨带的数据会出问题。中国横跨 UTM 49-53 五个带通信数据覆盖多个省份是常事用 UTM 得拆开来算麻烦。Equirectangular 不分区整个数据集用同一个参考纬度投影没有带边界的问题。投影后的平面坐标虽然本身有变形高纬度区东西方向被拉长但在 KD-Tree 里只用来筛候选不是最终结果所以变形不影响精度。参考纬度取所有点的平均纬度这样投影变形在数据集范围内整体最小。KD-Tree Haversine 两级筛选只用 KD-Tree 在投影空间算欧氏距离在地理坐标系里不够准投影变形。只算 Haversine每两个点都算一遍球面距离一万个点就是五千万次计算跑不动。做法是先用 KD-Tree 筛出 N×3 个候选最少 10 个然后用 Haversine 精算这些候选的真实球面距离按真实距离排序取前 N 个。步骤算法时间复杂度作用投影EquirectangularO(N)把经纬度转到平面米坐标建索引KD-Tree (nanoflann)O(N log N)空间索引初筛KD-Tree KNNO(N log N)每点取 N×3 个近邻精算Haversine 球面距离O(N × N×3)精确球面距离排序std::sortO(N × M log M)取前 N 个N×3 这个倍数是经验值。试下来 3 倍 保底 10 个在绝大多数场景下能保证 KD-Tree 投影空间里的前几名和真实球面距离的前几名一致。双表的差异双表比单表简单一些单表要排除自己j i 跳过因为自己离自己距离 0双表不用排除直接在表 2 的 KD-Tree 里查就行查出来的都是另一张表的点参考纬度取两个表所有点的平均值保证投影一致性双表场景很常见拿现网站址表去匹配规划站点或者两个不同时期的数据找对应关系。和暴力遍历的对比下面是用真实数据跑的时间对比。测试机配置i7-12700HRelease 编译。单表10 万个点各找最近 1 个算法耗时说明暴力双层循环O(N²)~85 秒N100k一亿次 HaversineKD-Tree本工具~1.8 秒含建树和精算双表表 1 一万点 × 表 2 十万点各找最近 3 个算法耗时说明暴力遍历O(N×M)~57 秒一千万次 HaversineKD-Tree本工具~0.6 秒表 2 建树表 1 逐行查询不同数据量下的表现数据集规模暴力遍历本工具提速倍数1,000 点0.07s0.01s~7×10,000 点5.2s0.08s~65×100,000 点520s1.8s~280×1,000,000 点不现实~32s—数据量越大提速越明显。暴力法是 O(N²) 增长KD-Tree 接近 O(N log N)。KD-Tree 建树的额外开销约 0.2 秒十万点平摊到每次查询可以忽略。和几种常见做法的比较方法 1SQLite Spatialite / PostGIS数据库空间索引R-Tree理论上也能做最近邻查询。但实际用起来的问题数据要先导入数据库查完再导回表格多两步操作通信工参表格式五花八门每次都要调导入配置插件的数据源就是剪贴板用户从 WPS/Excel 复制算完粘贴回去不需要管数据库本工具直接从剪贴板读算完写回剪贴板省掉导入导出。方法 2Python (shapely scipy.spatial)Python 生态有scipy.spatial.KDTree和shapely算法能力差不多。但插件的用户是通信工程师不是程序员。装 Python 环境、装包、写脚本大部分人不会去折腾。插件装在 WPS/Excel 里点一下按钮就出结果。方法 3H3 六边形网格索引H3 可以把经纬度映射到六边形通过网格 ID 快速找相邻格子里的点。工具里的覆盖分析标签页确实用了 H3但 H3 不适合做精确的 KNN网格边界附近的点容易漏掉需要查周边多圈精度受网格层级限制低层级不够细高层级网格数爆炸找最近 N 个点不如 KD-Tree 直接H3 更适合密度统计、热力图这类需要聚合的场景。精度KD-Tree 筛出来的 N×3 个候选经 Haversine 精算后取前 N 个精度和纯 Haversine 暴力算完全一致都基于球面模型。两个数据源在 100 公里范围内测试约 1° 跨度对比纯 Haversine 暴力计算结果最近点匹配完全一致。到 500 公里范围约 5° 跨度匹配一致率仍大于 99.9%极少出现因 Equirectangular 投影变形导致筛漏的情况且漏掉的点距离排在第 N1 位差异可以忽略。表格工具点击下载文件
解决的问题通信规划中经常要算哪个基站离我最近、“这批站点周围有哪些别的站点”。数据量上来以后逐条遍历算距离会很慢。工具做了两个标签页最近站点1单表同一张表里每行找最近的 N 个点最近站点2双表一张表的每个点去另一张表找最近的 N 个点下面说算法怎么做的以及为什么这样做。算法流程两个标签页共用一套逻辑原始经纬度 │ ▼ Equirectangular 投影 → 平面坐标米 │ ▼ KD-Tree 建索引 │ ▼ KNN 搜索取 N×3 个候选最少 10 个 │ ▼ Haversine 公式精算 → 按真实距离排序 → 取前 N 个 │ ▼ 输出到剪贴板几个设计点的意图Equirectangular 投影不用 UTM投影选的是等距圆柱投影Equirectangular公式很简单x lon × 111320 × cos(refLat) y lat × 111320UTM 要分带跨带的数据会出问题。中国横跨 UTM 49-53 五个带通信数据覆盖多个省份是常事用 UTM 得拆开来算麻烦。Equirectangular 不分区整个数据集用同一个参考纬度投影没有带边界的问题。投影后的平面坐标虽然本身有变形高纬度区东西方向被拉长但在 KD-Tree 里只用来筛候选不是最终结果所以变形不影响精度。参考纬度取所有点的平均纬度这样投影变形在数据集范围内整体最小。KD-Tree Haversine 两级筛选只用 KD-Tree 在投影空间算欧氏距离在地理坐标系里不够准投影变形。只算 Haversine每两个点都算一遍球面距离一万个点就是五千万次计算跑不动。做法是先用 KD-Tree 筛出 N×3 个候选最少 10 个然后用 Haversine 精算这些候选的真实球面距离按真实距离排序取前 N 个。步骤算法时间复杂度作用投影EquirectangularO(N)把经纬度转到平面米坐标建索引KD-Tree (nanoflann)O(N log N)空间索引初筛KD-Tree KNNO(N log N)每点取 N×3 个近邻精算Haversine 球面距离O(N × N×3)精确球面距离排序std::sortO(N × M log M)取前 N 个N×3 这个倍数是经验值。试下来 3 倍 保底 10 个在绝大多数场景下能保证 KD-Tree 投影空间里的前几名和真实球面距离的前几名一致。双表的差异双表比单表简单一些单表要排除自己j i 跳过因为自己离自己距离 0双表不用排除直接在表 2 的 KD-Tree 里查就行查出来的都是另一张表的点参考纬度取两个表所有点的平均值保证投影一致性双表场景很常见拿现网站址表去匹配规划站点或者两个不同时期的数据找对应关系。和暴力遍历的对比下面是用真实数据跑的时间对比。测试机配置i7-12700HRelease 编译。单表10 万个点各找最近 1 个算法耗时说明暴力双层循环O(N²)~85 秒N100k一亿次 HaversineKD-Tree本工具~1.8 秒含建树和精算双表表 1 一万点 × 表 2 十万点各找最近 3 个算法耗时说明暴力遍历O(N×M)~57 秒一千万次 HaversineKD-Tree本工具~0.6 秒表 2 建树表 1 逐行查询不同数据量下的表现数据集规模暴力遍历本工具提速倍数1,000 点0.07s0.01s~7×10,000 点5.2s0.08s~65×100,000 点520s1.8s~280×1,000,000 点不现实~32s—数据量越大提速越明显。暴力法是 O(N²) 增长KD-Tree 接近 O(N log N)。KD-Tree 建树的额外开销约 0.2 秒十万点平摊到每次查询可以忽略。和几种常见做法的比较方法 1SQLite Spatialite / PostGIS数据库空间索引R-Tree理论上也能做最近邻查询。但实际用起来的问题数据要先导入数据库查完再导回表格多两步操作通信工参表格式五花八门每次都要调导入配置插件的数据源就是剪贴板用户从 WPS/Excel 复制算完粘贴回去不需要管数据库本工具直接从剪贴板读算完写回剪贴板省掉导入导出。方法 2Python (shapely scipy.spatial)Python 生态有scipy.spatial.KDTree和shapely算法能力差不多。但插件的用户是通信工程师不是程序员。装 Python 环境、装包、写脚本大部分人不会去折腾。插件装在 WPS/Excel 里点一下按钮就出结果。方法 3H3 六边形网格索引H3 可以把经纬度映射到六边形通过网格 ID 快速找相邻格子里的点。工具里的覆盖分析标签页确实用了 H3但 H3 不适合做精确的 KNN网格边界附近的点容易漏掉需要查周边多圈精度受网格层级限制低层级不够细高层级网格数爆炸找最近 N 个点不如 KD-Tree 直接H3 更适合密度统计、热力图这类需要聚合的场景。精度KD-Tree 筛出来的 N×3 个候选经 Haversine 精算后取前 N 个精度和纯 Haversine 暴力算完全一致都基于球面模型。两个数据源在 100 公里范围内测试约 1° 跨度对比纯 Haversine 暴力计算结果最近点匹配完全一致。到 500 公里范围约 5° 跨度匹配一致率仍大于 99.9%极少出现因 Equirectangular 投影变形导致筛漏的情况且漏掉的点距离排在第 N1 位差异可以忽略。表格工具点击下载文件
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
