7

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

有点难过如何处理这个问题。任何帮助将不胜感激。

4

4 回答 4

5

找到包含所有点的最小圆，并将其半径与 100 进行比较。

于 2010-04-26T20:44:11.410 回答
1

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

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

X = R * cos(long) * cos(lat)

Y = R * sin(long) * 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)，角度为：

角度 = arcsin((V1 x V2) / (|V1||V2|))，其中 x 是叉积。

那么距离是：

dist = (地球周长) * 角度 / (2 * pi)

当然，这并没有考虑到海拔的变化或地球在赤道处更宽的事实。

很抱歉没有用 LaTeX 写我的数学。

于 2010-04-26T20:46:13.527 回答
1

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

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

请查看 Gupta 和 Saluja 的论文“应用程序在高斯球上的一些邻近问题的优化算法”中的第 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 部分。这部分展示了如何实际获得点的“最小封闭圆”。

要进行所需的二次规划，请参阅 ND Botkin 的论文“求解二次规划的随机算法”。本教程很有帮助，但论文使用 (1/2)x^TG x - g^T x，网络教程使用 (1/2)x^TH x + c^T x。一个添加术语，另一个减去，导致与符号相关的问题。另请参阅此示例 2D QP 问题。提示：如果您使用 C++，Eigen 库非常好。

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

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

于 2011-06-02T13:16:46.817 回答
0

查看这个问题的答案。它提供了一种测量任意两个（纬度、经度）点之间距离的方法。然后使用最小包围圆算法。

我怀疑在平面上找到一个最小的封闭圆可能已经够难了，所以为了消除处理经纬度和球面几何的微妙之处，您可能应该考虑将您的点映射到 XY 平面。这会引入一定程度的失真，但如果您的预期规模是 100 英里，您可能可以忍受。一旦在 XY 平面上有一个圆及其中心，您就可以随时映射回地球球体并重新检查您的距离。

于 2010-04-26T20:45:48.630 回答