寻找球体上最近的一对点
我知道如何针对 2D 情况（x 和 y）实现 n log n 个最接近的点对算法（Shamos 和 Hoey）。然而，对于给定纬度和经度的问题，无法使用此方法。两点之间的距离是使用半正矢公式计算的。
我想知道是否有某种方法可以将这些纬度和经度转换为各自的 x 和 y 坐标并找到最接近的点对，或者是否有另一种技术可以用来做到这一点。
I know how to implement n log n closest pair of points algorithm (Shamos and Hoey) for 2D cases (x and y). However for a problem where latitude and longitude are given this approach cannot be used. The distance between two points is calculated using the haversine formula.
I would like to know if there is some way to convert these latitudes and longitudes to their respective x and y coordinates and find the closest pair of points, or if there is another technique that can be used to do it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我会将它们转换为三维坐标，然后使用 分而治之使用平面而不是直线的方法。这肯定会正确工作。我们可以确信这一点，因为当仅检查球体上的点时，弧距（在表面上行走的距离）最近的两个点也将是 3-d 笛卡尔距离最近的两个点。这将有运行时间 O(nlogn)。
要转换为 3 维坐标，最简单的方法是将 (0,0,0) 设为地球中心，然后坐标为 (cos(lat)*cos(lon),cos(lat)*sin(lan ），罪（纬度））。出于这些目的，我使用地球半径为 1 的比例来简化计算。如果您想要使用其他单位的距离，只需将所有数量乘以以该单位测量的地球半径即可。
我应该指出，所有这些都假设地球是一个球体。这并不完全是一个，而且点实际上也可能有高度，所以这些答案不会完全准确，但在几乎所有情况下它们都非常接近正确。
I would translate them to three dimensional coordinates and then use the divide and conquer approach using a plane rather than a line. This will definitely work correctly. We can be assured of this because when only examining points on the sphere, the two closest points by arc distance (distance walking over the surface) will also be the two closest by 3-d Cartesian distance. This will have running time O(nlogn).
To translate to 3-d coordinates, the easiest way is to make (0,0,0) the center of the earth and then your coordinates are (cos(lat)*cos(lon),cos(lat)*sin(lan),sin(lat)). For those purposes I'm using a scale for which the radius of the Earth is 1 in order to simplify calculations. If you want distance in some other unit, just multiply all quantities by the radius of the Earth when measured in that unit.
I should note that all this assumes that the earth is a sphere. It's not exactly one and points may actually have altitude as well, so these answers won't really be completely exact, but they will be very close to correct in almost every case.