我有一个程序，输入是一组纬度/经度点的数组。我需要对该数组执行检查，以确保所有点都在某个半径内。例如，最大允许半径为100英里。给定一组纬度/经度（来自MySQL数据库，可能有10个点或10000个点），我需要找出它们是否都适合一个半径为100英里的圆中。
对此我感到困惑，不知道如何处理。非常感谢您的帮助。
对此我感到困惑，不知道如何处理。非常感谢您的帮助。
多个经纬度点的半径
7
- user301410
5
找到任何给定点集的中心是我尚未尝试解决的问题，但一旦你解决了这个问题，Haversine公式将帮助你确定它们是否在半径范围内。 - jball
中心点难道不只是具有各个纬度和经度的平均值吗？还是说我忽略了球面几何的某些微妙之处？ - las3rjock
中心点被称为重心。然而，这并没有帮助我们，因为它并不是包含所有点的最小圆的中心（想象一下右边有很多点，左边只有一个点-重心会在右边，但圆的中心将在中间）。 - BlueRaja - Danny Pflughoeft
如描述的那样，您想做的事情可能与找到包含您的点的最小圆一样困难。这是一个棘手的问题（虽然不是不可能）。在这种情况下，我会重新审查原始要求，看看是否有另一种计算方法可以解决真正的根本问题。您可能不想浪费开发和 CPU 时间来解决一个精确的数学问题，而该问题本身只是对一些模糊规定的近似。 - sigfpe
2@las3jrock：在纬度相同的两点之间的中心将位于45度纬度上方。想象一下飞机的航线在墨卡托地图上“弯曲”，尽管它实际上是直线行驶。 - Mashmagar
4个回答
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），则角度为：
angle = arcsin((V1 x V2) / (|V1||V2|))，其中x是叉积。
然后距离为：
dist =（地球周长）*角度/（2 * pi）
当然，这并没有考虑到高程的变化或地球在赤道处更宽的事实。抱歉没有用LaTeX编写我的数学。
- Mashmagar
1
下面的回答涉及假装地球是一个完美的球体，这应该比将地球视为平面给出更准确的答案。
要计算一组纬度/经度点的半径，必须先确保您的点集是“半球形”的，即所有点都可以放入某个任意半球形状中。
请参阅Gupta和Saluja的论文“Optimal algorithms for some proximity problems on the Gaussian sphere with applications”第3节。我没有具体的链接，但我相信您可以在网上免费找到副本。这篇论文不足以实现解决方案。您还需要Ha和Yoo的“Approximating Centroids for the Maximum Intersection of Spherical Polygons”的附录1。
我不会使用Megiddo算法来执行半球性测试的线性规划部分。相反，使用Seidel算法解决线性规划问题，这在Raimund Seidel的“Small-Dimensional Linear Programming and Convex Hulls Made Easy”中有描述。还请参阅Kurt Mehlhorn的“Seidel’s Randomized Linear Programming Algorithm”和Christer Ericson的“Real-Time Collision Detection”的第9.4节。
要计算一组纬度/经度点的半径，必须先确保您的点集是“半球形”的，即所有点都可以放入某个任意半球形状中。
请参阅Gupta和Saluja的论文“Optimal algorithms for some proximity problems on the Gaussian sphere with applications”第3节。我没有具体的链接，但我相信您可以在网上免费找到副本。这篇论文不足以实现解决方案。您还需要Ha和Yoo的“Approximating Centroids for the Maximum Intersection of Spherical Polygons”的附录1。
我不会使用Megiddo算法来执行半球性测试的线性规划部分。相反，使用Seidel算法解决线性规划问题，这在Raimund Seidel的“Small-Dimensional Linear Programming and Convex Hulls Made Easy”中有描述。还请参阅Kurt Mehlhorn的“Seidel’s Randomized Linear Programming Algorithm”和Christer Ericson的“Real-Time Collision Detection”的第9.4节。
一旦确定您的点是半球形的，请转到Gupta和Saluja的论文第4节。该部分展示了如何实际获取点的“最小包围圆”。
要执行所需的二次规划，请参阅N.D. Botkin的论文“解决二次规划的随机算法”。此教程很有帮助，但是论文使用（1/2）x ^ T G x-g ^ T x，而Web教程使用（1/2）x ^ T H x + c ^ T x。一个添加术语，另一个减去术语，导致与符号相关的问题。还请参见此2D QP问题示例。提示：如果您正在使用C ++，则Eigen库非常好。
这种方法比上面一些2D方法略微复杂，但它应该比完全忽略地球曲率更准确地给出结果。此方法的时间复杂度也为O（n），可能是渐近最优的。
注意：上述方法可能无法很好地处理重复数据，因此在查找最小包围圆之前，您可能需要检查重复的纬度/经度点。
- bnsmith
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接