Douglas-Peucker -球面上从一点到圆的最短弧

Question

我在各种编程语言中看到了许多使用Douglas-Peucker polyline简化算法来生成在Google Maps上使用的GPolyline的示例。当表示平面上的多段线时，该算法涉及计算点和线(通过另外两个点)之间的距离。

到目前为止，我看到的所有示例都以一种非常天真的方式应用了算法，简单地将x和y替换为纬度和经度。只要折线非常局部化，不太靠近杆子，并且不越过180°子午线，这可能会产生可接受的结果，但我想实现一个更通用的算法版本。

因此，如果我没有记错的话，我需要计算球体表面上最短圆弧的长度，即从一点到通过球体表面另外两个点的圆，圆心与球体(地球)的中心重合。

有人知道计算这个长度的公式吗？

提前感谢

Answer 1

我将尝试用单位向量p、q和r来表示所有内容，这些单位向量可以被认为是以原点<>e29>为中心的单位球体Σ代码上的点。您可以通过按地球半径放大来将其转换为地面量。有一些background material here。

我们想要找出从p到大圆C的大圆距离d，通过q和r。C是平面P和球体的交集，其中P是通过Q<Σ>E228，r和原点的平面。D是p和P之间的角度θ(以弧度表示)。P的法向量是归一化的叉积q×r/sinφ，，其中φ是q和r之间的角度。

我们最终会得到

θ= arcsin(p⋅(q×r)/sinφ)

就像我说的，这里的一切都被地球半径R放大了。所以这三个点是Rp，Rq，Rr，距离是Rθ。

但是，如果您只想找到一个距离最短的点/线组合，则可以省略乘以R。实际上，您可以省略p⋅(q×r)/sinφ. ()，只查看arcsin的相对大小