多个纬度/经度点的半径

Question

我有一个程序，需要输入一个纬度/长点的数组。我需要对该阵列执行检查，以确保所有点都在特定半径内。因此，例如，我允许的最大半径是100英里。给定一个经纬度数组（来自MySQL数据库，可能是10点可能是10000）我需要弄清楚它们是否都适合一个半径为100英里的圆。

有点难倒如何解决这个问题。任何帮助将不胜感激。

Answer 1

查找the smallest circle containing all points，其半径出答案比较100

Answer 2

检查到this question。它提供了一种方法来测量任意两个（经纬度）点之间的距离。然后使用smallest enclosing circle algorithm。

我怀疑找到一个最小的封闭圆可能在一个平面上足够困难，所以为了消除处理经纬度和球面几何的细微之处，您应该考虑将您的点映射到XY平面。这会导致一定程度的失真，但如果您的预定比例是100英里，那么您可以忍受这一点。一旦你在XY平面上有一个圆圈和中心，你总是可以映射回地球球体并重新检查你的距离。

Answer 3

对我来说，解决这个问题最简单的方法是将坐标转换为（X，Y，Z），然后找到沿着球体的距离。

假设地球是一个球体（完全不真实）半径为R ...

X = R * cos（长）* COS（LAT）

Y = R * SIN（长）* COS （LAT）

Z = R * SIN（LAT）

此时，可以近似使用用于三维空间勾股定理的延长线上的点之间的距离：

dist = sqrt（（x1-x2）^ 2 +（y1-y2）^ 2 +（z1-z2）^ 2）

但是要找到沿表面的实际距离，您需要知道从原点（地球中心）两点对着的角度。

代表作为矢量的位置V1 =（X1，Y1，Z1）和V2 =（X2，Y2，Z2），该角度是：

角=反正弦（（V1 X V2）/（| V1 || V2 |）），其中x是叉积。

的距离，则：

DIST =（地球的周长）*角度/（2 * PI）

当然，这没有考虑到在高程帐户更改或一个事实，即地球在赤道更宽。

不要在LaTeX写我的数学道歉。

Answer 4

下面的答案涉及假装地球是一个完美的球体，应该给出比将平面视为平面更准确的答案。

要确定一组经纬度点的半径，首先必须确保您的一组点是“半球”，即。所有的点都可以适合你的完美球体的任意一半。

请参阅Gupta和Saluja在论文“Optimal algorithms for some proximity problems on the Gaussian sphere with applications”中的第3节。我没有特定的链接，但我相信你可以在网上免费找到一份副本。本文不足以实施解决方案。 Ha和Yoo还需要附录1中的“近似球形多边形的最大交点的质心”。

我不会使用Megiddo的算法来完成半球测试的线性编程部分。相反，使用Seidel的算法来解决线性规划问题，如Raimund Seidel的“Small-Dimensional Linear Programming and Convex Hulls Made Easy”所述。另请参见Kurt Mehlhorn的“Seidel的随机线性规划算法”和Christer Ericson的“实时碰撞检测”第9.4节。

一旦你确定你的点是半球形的，移动到Gupta和Saluja的论文的第4部分。这部分展示了如何实际得到点的“最小封闭圆”。

要做所需的二次规划，请参阅N.D.Botkin撰写的论文“解决二次规划的随机算法”。 This tutorial是有帮助的，但本文使用（1/2）x^T G x - g^T x和Web教程使用（1/2）x^T H x + c^T x。一个增加了术语和其他减法，导致符号相关的问题。 Also see this example 2D QP problem。提示：如果你使用C++，Eigen库是非常好的。

这种方法比上面的一些2D方法稍微复杂一点，但它应该给你比只是完全忽略地球曲率更准确的结果。这种方法也具有O（n）时间复杂度，这可能是渐近最优的。

注意：上述方法可能无法很好地处理重复数据，因此您可能希望在查找最小的封闭圆之前检查重复的经纬度点。