集的经度/纬度点之间最大距离 [英] Greatest distance between set of longitude/latitude points

问题描述

我有一组液化天然气/纬度坐标。这将是计算所述集合（以下简称最大直径如果你愿意）任意两点之间的最大距离的一个有效的方法？

一个幼稚的方法是使用半正矢公式计算每个2点之间的距离，并得到最大的，但是这并不能很好地扩展明显。

编辑：点位于一个足够小的区域，测量，其中一人携带的移动设备在一天的课程是活跃的区域

解决方案

我觉得下面可能是一个有用的近似值，其中线性扩展，而不是二次配点的数量，是很容易实现的：

1. 计算的点质量M中心
2. 找到点P <子> 0 ，有到M的最大距离
3. 找到点P <子> 1 有与P的最大距离<子> 0
4. 近似P <子> 0 和P <子> 1
之间的最大直径的距离

这可以通过重复步骤3 N次一概而论， 并采取P的距离<子> N-1 和P <子> N

步骤1，可以进行有效地接近中号为经度和纬度的平均水平，这是确定，当距离是小，而两极足够远。其它步骤可以进行使用的确切距离式，但它们要快​​得多，如果点'坐标可以被近似为躺在一个平面。一旦遥远一对（希望该对的最大距离），已经发现，它的距离可以被重新计算的确切配方

近似的一个例子可以是以下内容：如果φ（M）和λ（M）是纬度和质量中心计算为Σφ（P）的经度/ n和Σλ（P）/ n时，

• X（P）=（λ（P） - λ（M）+ C）COS（φ（P））
• Y（P）=φ（P） - φ（M）[这仅仅是为了清楚起见，它也可以简单地为y（P）=φ（P）]

其中，C是通常为0，但也可以是±360°，如果组点穿过λ=±180°线。要查找的最大距离你只需要找到

• MAX（（X（P <子> N ） - X（P <子> N-1 ）） ² +（Y（P <子> ñ） - Y（P <子> N-1 ）） ² ）

（你不需要的平方根，因为它是单调的）

的相同的坐标变换可用于以有更好的起点重复步骤1（新的坐标系中）。我猜想，如果某些条件得到满足，上述步骤（没有重复步骤3）总是导致真正遥远的一双（我的术语）。如果我只知道的这的条件...

编辑：

我讨厌建立在别人的解决方案，但有人将不得不这样做。

仍将其保持上述4个步骤，可任选地（但可能是有益的，这取决于点的典型分布）步骤3的重复， 和之后的<一href="http://stackoverflow.com/questions/16865291/greatest-distance-between-set-of-lng-lat-points/16870359#16870359">solution Spacedman 的， 做计算的3D克服封闭性和距离的限制，从极：

• X（P）= SIN（φ（P））
• Y（P）= COS（φ（P））罪（λ（P））
• ž（P）= COS（φ（P））COS（λ（P））

（唯一近似的是，这仅保存一个完美的球体）

质心为x（M）=ΣX（P）/ n等给出， 而最大的一个人是寻找

• MAX（（X（P <子> N ） - X（P <子> N-1 ）） ² +（Y（P <子> ñ） - Y（P <子> N-1 ）） ² +（Z（P <子> N ） - Z（P <子> N-1 ）） ² ）

所以：你第一次转换球笛卡尔坐标，然后从质量中心开始，发现，在至少两个步骤（步骤2和3），最远点从preceding点。只要你可以重复步骤3随着距离的增加，也许重复的最大数量，但不会带你远离当地的最大值。从质心开始是有很大帮助没有，或者说，如果点有s $ P $垫到整个地球。

编辑2：

我学会了足够的R键写下算法的核心（好的语言进行数据分析！）

有关的平面近似，围绕λ忽略这个问题=±180°线：

 ＃输入：LNG，纬度（矢量）
弧度= PI / 180;
X =（LNG  - 平均（LNG））* COS（纬度*弧度）
Y =（纬度 - 平均（LAT））
I = which.max（（X  - 均值（X））^ 2 +（Y）^ 2）
J = which.max（（X  -  X [I]）^ 2 +（Y  -  Y [I]）^ 2）
＃输出：I，J（指数）
 

在我的电脑，找到索引它需要不到一秒钟我和Ĵ达到1000000个。< BR>下面的3D版是有点慢，但适用于点的任意分布（且不需要进行修改时，λ=±180°线交叉）：

 ＃输入：LNG，纬度
弧度=圆周率/ 180
X =罪（LAT * RAD）
F = COS（LAT * RAD）
Y = SIN（LNG * RAD）*˚F
Z = COS（LNG * RAD）*˚F
I = which.max（（X  - 平均值（X））^ 2 +（Y  - 平均（γ））^ 2 +（Z  - 平均（Z））^ 2）
J = which.max（（X  -  X [I]）^ 2 +（Y  -  Y [I]）^ 2 +（Z  -  Z [i]）^ 2）
K = which.max（（X  -  X [J]）^ 2 +（Y  -  Y [J]）^ 2 +（Z  -  Z [J]）^ 2）＃可选
＃输出：J，K（或I，J）
 

k的计算可以被排除在外（即，其结果可能是由给我和Ĵ），根据数据和上的要求。另一方面，我的实验已经表明，计算一个进一步指数是无用的。

有应该记住的是，在任何情况下，所得到的点之间的距离是一个估计值，它是一个下限直径的集合的，尽管它很经常将是直径本身（的如何的常取决于数据。）

修改3：

不幸的是，平面近似的相对误差可以，在极端情况下，会高达1-1 /√3＆cong; 42.3％，这可能是不可接受的，即使非常罕见的。该算法可以以具有上限的约20％，这是我由罗盘和直边（解析解是麻烦的）衍生进行修改。修改后的算法找到一对点的蒙山局部最大距离，然后重复同样的步骤，但与第一对的中点此时开始，可能找到一个不同的对

 ＃输入：LNG，纬度
弧度=圆周率/ 180
X =（LNG  - 平均（LNG））* COS（纬度*弧度）
Y =（纬度 - 平均（LAT））
i.n_1 = 1＃N_1：N-1
x.n_1 =平均（x）的
y.n_1 = 0 =意思是（Y）
s.n_1 = 0＃S：距离的平方
重复 {
   S =（X  -  x.n_1）^ 2 +（Y  -  y.n_1）^ 2
   i.n = which.max（S）
   x.n = X [i.n]
   y.n = Y [i.n]
   S.N = S [i.n]
   如果（S.N＆LT; = s.n_1）破
   i.n_1 = i.n
   x.n_1 = x.n
   y.n_1 = y.n
   s.n_1 = S.N
}
i.m_1 = 1
x.m_1 =（x.n + x.n_1）/ 2
y.m_1 =（y.n + y.n_1）/ 2
s.m_1 = 0
m_ok = TRUE
重复 {
   S =（X  -  x.m_1）^ 2 +（Y  -  y.m_1）^ 2
   肌内= which.max（S）
   如果（肌内== i.n ||肌内== i.n_1）{m_ok = FALSE;打破 }
   x.m = X [肌内]
   y.m = Y [肌内]
   S.M = S [肌内]
   如果（S.M＆LT; = s.m_1）破
   i.m_1 =肌内
   x.m_1 = x.m
   y.m_1 = y.m
   s.m_1 = S.M
}
如果（m_ok＆安培;＆安培; S.M＆GT; S.N）{
   I =肌内
   J = i.m_1
} 其他 {
   I = i.n
   J = i.n_1
}
＃输出：I，J
 

的三维算法可以以类似的方式被修改。它是可能的（无论是在2D和在3D的情况下），以从所述第二对点的中点重新开始再次（如果找到）。该上限在这种情况下将作为练习留给读者： - ）

与（太）简单的算法改进算法的比较表明，正常和广场均匀分布，处理时间几乎增加了一倍，从1.6％降低平均误差为0.03％（订单级）。从一个中点结果的进一步启动一个刚刚稍微好一点的平均误差，但几乎相等的最大误差。

修改4：

我要学习这篇文章然而，但它看起来像20％，我发现了指南针和直尺实际上是在1-1 /√（5-2√3）≅19.3％

I have a set of lng/lat coordinates. What would be an efficient method of calculating the greatest distance between any two points in the set (the "maximum diameter" if you will)?

A naive way is to use Haversine formula to calculate the distance between each 2 points and get the maximum, but this doesn't scale well obviously.

Edit: the points are located on a sufficiently small area, measuring the area in which a person carrying a mobile device was active in the course of a single day.

解决方案

I think that the following could be a useful approximation, which scales linearly instead of quadratically with the number of points, and is quite easy to implement:

1. calculate the center of mass M of the points
2. find the point P₀ that has the maximum distance to M
3. find the point P₁ that has the maximum distance to P₀
4. approximate the maximum diameter with the distance between P₀ and P₁

This can be generalized by repeating step 3 N times, and taking the distance between P_N-1 and P_N

Step 1 can be carried out efficiently approximating M as the average of longitudes and latitudes, which is OK when distances are "small" and the poles are sufficiently far away. The other steps could be carried out using the exact distance formula, but they are much faster if the points' coordinates can be approximated as lying on a plane. Once the "distant pair" (hopefully the pair with the maximum distance) has been found, its distance can be re-calculated with the exact formula.

An example of approximation could be the following: if φ(M) and λ(M) are latitude and longitude of the center of mass calculated as Σφ(P)/n and Σλ(P)/n,

• x(P) = (λ(P) - λ(M) + C) cos(φ(P))
• y(P) = φ(P) - φ(M) [ this is only for clarity, it can also simply be y(P) = φ(P) ]

where C is usually 0, but can be ± 360° if the set of points crosses the λ=±180° line. To find the maximum distance you simply have to find

• max((x(P_N) - x(P_N-1))² + (y(P_N) - y(P_N-1))²)

(you don't need the square root because it is monotonic)

The same coordinate transformation could be used to repeat step 1 (in the new coordinate system) in order to have a better starting point. I suspect that if some conditions are met, the above steps (without repeating step 3) always lead to the "true distant pair" (my terminology). If I only knew which conditions...

EDIT:

I hate building on others' solutions, but someone will have to.

Still keeping the above 4 steps, with the optional (but probably beneficial, depending on the typical distribution of points) repetition of step 3, and following the solution of Spacedman, doing calculations in 3D overcomes the limitations of closeness and distance from poles:

• x(P) = sin(φ(P))
• y(P) = cos(φ(P)) sin(λ(P))
• z(P) = cos(φ(P)) cos(λ(P))

(the only approximation is that this holds only for a perfect sphere)

The center of mass is given by x(M) = Σx(P)/n, etc., and the maximum one has to look for is

• max((x(P_N) - x(P_N-1))² + (y(P_N) - y(P_N-1))² + (z(P_N) - z(P_N-1))²)

So: you first transform spherical to cartesian coordinates, then start from the center of mass, to find, in at least two steps (steps 2 and 3), the farthest point from the preceding point. You could repeat step 3 as long as the distance increases, perhaps with a maximum number of repetitions, but this won't take you away from a local maximum. Starting from the center of mass is not of much help, either, if the points are spread all over the Earth.

EDIT 2:

I learned enough R to write down the core of the algorithm (nice language for data analysis!)

For the plane approximation, ignoring the problem around the λ=±180° line:

# input: lng, lat (vectors)
rad = pi / 180;
x = (lng - mean(lng)) * cos(lat * rad)
y = (lat - mean(lat))
i = which.max((x - mean(x))^2 + (y       )^2)
j = which.max((x - x[i]   )^2 + (y - y[i])^2)
# output: i, j (indices)

On my PC it takes less than a second to find the indices i and j for 1000000 points.
The following 3D version is a bit slower, but works for any distribution of points (and does not need to be amended when the λ=±180° line is crossed):

# input: lng, lat
rad = pi / 180
x = sin(lat * rad)
f = cos(lat * rad)
y = sin(lng * rad) * f
z = cos(lng * rad) * f
i = which.max((x - mean(x))^2 + (y - mean(y))^2 + (z - mean(z))^2)
j = which.max((x - x[i]   )^2 + (y - y[i]   )^2 + (z - z[i]   )^2)
k = which.max((x - x[j]   )^2 + (y - y[j]   )^2 + (z - z[j]   )^2) # optional
# output: j, k (or i, j)

The calculation of k can be left out (i.e., the result could be given by i and j), depending on the data and on the requirements. On the other hand, my experiments have shown that calculating a further index is useless.

It should be remembered that, in any case, the distance between the resulting points is an estimate which is a lower bound of the "diameter" of the set, although it very often will be the diameter itself (how often depends on the data.)

EDIT 3:

Unfortunately the relative error of the plane approximation can, in extreme cases, be as much as 1-1/√3 ≅ 42.3%, which may be unacceptable, even if very rare. The algorithm can be modified in order to have an upper bound of approximately 20%, which I have derived by compass and straight-edge (the analytic solution is cumbersome). The modified algorithm finds a pair of points whith a locally maximal distance, then repeats the same steps, but this time starting from the midpoint of the first pair, possibly finding a different pair:

# input: lng, lat
rad = pi / 180
x = (lng - mean(lng)) * cos(lat * rad)
y = (lat - mean(lat))
i.n_1 = 1 # n_1: n-1
x.n_1 = mean(x)
y.n_1 = 0 # = mean(y)
s.n_1 = 0 # s: square of distance
repeat {
   s = (x - x.n_1)^2 + (y - y.n_1)^2
   i.n = which.max(s)
   x.n = x[i.n]
   y.n = y[i.n]
   s.n = s[i.n]
   if (s.n <= s.n_1) break
   i.n_1 = i.n
   x.n_1 = x.n
   y.n_1 = y.n
   s.n_1 = s.n
}
i.m_1 = 1
x.m_1 = (x.n + x.n_1) / 2
y.m_1 = (y.n + y.n_1) / 2
s.m_1 = 0
m_ok  = TRUE
repeat {
   s = (x - x.m_1)^2 + (y - y.m_1)^2
   i.m = which.max(s)
   if (i.m == i.n || i.m == i.n_1) { m_ok = FALSE; break }
   x.m = x[i.m]
   y.m = y[i.m]
   s.m = s[i.m]
   if (s.m <= s.m_1) break
   i.m_1 = i.m
   x.m_1 = x.m
   y.m_1 = y.m
   s.m_1 = s.m
}
if (m_ok && s.m > s.n) {
   i = i.m
   j = i.m_1
} else {
   i = i.n
   j = i.n_1
}
# output: i, j

The 3D algorithm can be modified in a similar way. It is possible (both in the 2D and in the 3D case) to start over once again from the midpoint of the second pair of points (if found). The upper bound in this case is "left as an exercise for the reader" :-).

Comparison of the modified algorithm with the (too) simple algorithm has shown, for normal and for square uniform distributions, a near doubling of processing time, and a reduction of the average error from .6% to .03% (order of magnitude). A further restart from the midpoint results in an a just slightly better average error, but almost equal maximum error.

EDIT 4:

I have to study this article yet, but it looks like the 20% I found with compass and straight-edge is in fact 1-1/√(5-2√3) ≅ 19.3%

这篇关于集的经度/纬度点之间最大距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！