道格拉斯 - 皮克（Douglas-Peucker） - 球体表面上从一个点到一个圆的最短弧 [英] Douglas-Peucker - Shortest arc from a point to a circle, on the surface of a sphere

问题描述

我已经看到很多使用Douglas-Peucker多义线简化算法生成GPolyline的各种编程语言的例子，以便在Google Maps上使用。
当计划中的多义线表示算法时，算法包括计算点与线之间的距离（通过其他两个点）。

现在我所看到的所有例子都是以非常天真的方式应用算法，只需用经度和纬度代替x和y即可。这可能会产生可接受的结果，只要折线是非常局部化的，不太接近极点，并且不会穿过180°子午线，但是我想实现更通用的算法。

因此，如果我没有弄错，我需要计算球体表面上最短的弧的长度，从一点到通过表面的其他两点这个球体的中心与球体中心（地球）重合。

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

在此先感谢

解决方案

我会尝试用单位向量来表示一切<强> p ， q 和 r ，可以将其视为单位球体上的点Σ 来源 0 。您可以通过按地球半径放大将其转换为地面数量。这里有一些背景资料。

我们希望找到 p 到大圆 C 的大圆距离 d ，通过 q 和 r 。 C 是平面 P 和球体Σ 的交点，其中 P 是通过的平面 q ， r 和原始 0 。 d 只是角度θ; （以弧度表示）在 p 和 P 之间。对于 P 的法向量是归一化的交叉乘积 q &次; r / sin&phi ;,其中φ是 q 和 r 之间的角度。

我们最终得到了

θ = arcsin（ p ⋅（ q × r ）/ sinφ）

<正如我所说的，这里的一切都会被地球半径R em加大。所以这三点是* R *** p **，* R *** q **，* R *** r **，距离是R θ。

但是，如果您只想找到最短距离的点/线组合，则可以省略乘以 R 。事实上，你可以省略arcsin（），看看 p ⋅（ q × r ）/ sin&phi ;。

I have seen many examples in various programming languages that are using the Douglas-Peucker polyline simplification algorithm to produce a GPolyline to be used on Google Maps. The algorithm, when expressed for polylines on a plan, involves the calculation of the distance between a point and a line (passing through two other points).

Now all the examples I have seen so far are applying the algorithm in a very naïve way, simply by replace x and y by the latitude and longitude. This may produce acceptable results as long as the polyline is very localized, not too close to a pole, and does not cross the 180° meridian, but I would like to implement a more general version of the algorithm.

So, If I am not mistaken, I would need to compute the length of the shortest arc on the surface of a sphere, from a point to the circle passing through two other points of the surface of the sphere, the center of which coinciding with the center of the sphere (the earth).

Does anyone know the formula that computes this length?

Thanks in advance

解决方案

I'll try to express everything in terms of unit vectors p, q, and r, which can be thought of as points on a unit sphere Σ centered at the origin 0. You can convert that to terrestrial quantities by scaling up by the radius of the earth. There is some background material here.

We want to find the great circle distance d from p to the great circle C going through q and r. C is the intersection of a plane P and the sphere Σ, where P is the plane that passes through q, r, and the origin 0. d is simply the angle θ (expressed in radians) between p and P. The normal vector for P is the normalized cross product q×r/sinφ, where φ is the angle between q and r.

We end up with

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

As I said, everything here gets scaled up by the radius R of the earth. So the three points are *R***p**, *R***q**, *R***r**, and the distance is Rθ.

However, if all you want is to find a point/line combo with the shortest distance, you can omit multiplying by R. In fact you can omit the arcsin() and just look at the relative sizes of the p⋅(q×r)/sinφ.

这篇关于道格拉斯 - 皮克（Douglas-Peucker） - 球体表面上从一个点到一个圆的最短弧的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！