沿路线查找兴趣点的算法？

Question

给定起点和终点之间的路线，如何沿着这条路线在最大距离 D_max 处有效地找到兴趣点 (POI)（由其长/纬度坐标给出）？

一种天真的方法是沿着这条路线移动一个半径为 D_max 的圆，然后在这个圆内寻找 POI；但如果圆圈不重叠，我们可能会忘记 POI，如果它们重叠，我们会多次找到相同的 POI，因此效率不高。

什么是更好的方法？

（注意：我不知道 SO 是否是这个问题的最佳位置，或者我是否应该 post 在 CS、软件工程或其他地方？）

Answer 1

您需要在 lat/lon 坐标和给定点中找到折线的距离，并将其与最大距离进行比较。

每个路段都可以获得交叉轨道距离（GI在图片中）from here：

Formula:    dxt = asin( sin(δ13) ⋅ sin(θ13−θ12) ) ⋅ R
where    δ13 is (angular) distance from start point to third point
 θ13 is (initial) bearing from start point to third point
 θ12 is (initial) bearing from start point to end point
 R is the earth’s radius
JavaScript: var dXt = Math.asin(Math.sin(d13/R)*Math.sin(θ13-θ12)) * R;

以及沿轨距离（BI在图片）：

Formula:    dat = acos( cos(δ13) / cos(δxt) ) ⋅ R
where    δ13 is (angular) distance from start point to third point
 δxt is (angular) cross-track distance
 R is the earth’s radius
JavaScript: var dAt = Math.acos(Math.cos(d13/R)/Math.cos(dXt/R)) * R;

并将沿航迹距离与起点终点距离进行比较（如果为负数或更大，则最近点为线段终点 - 图片中的BH情况，此处HC是BC段的最小距离）

方位和距离计算在同一页上。

如果您正在使用一些地理库，它们应该包含用于此类任务的函数。

Answer 2

假设您的 POI 点在某些 space 分区数据结构中作为 k-d 树或四叉树编制索引，实施 find-points-near-polyline 算法应该不会太困难。

从折线中获取符合它的线段集。
递归下降到您的 space 分区数据结构中，根据到 space 分区封闭框的距离在每个级别过滤段集。
到达最终节点后，使用蛮力检查该点集合中剩余向量与分区中 POI 之间的距离。

沿路线查找兴趣点的算法？

Algorithm to find Points of Interest along a route?

algorithm

routing

geolocation