寻找最接近的对点上的球 [英] Finding closest pair of points on a sphere

问题描述

我知道如何实现N日志的N个最近对点算法（Shamos和霍伊）二维情况下（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.

我想知道是否有一些方法来转换这些经纬度到它们各自的X和Y坐标和找到最接近一对点，或者如果有另一种技术，可以用来做。

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.

推荐答案

我把它们翻译成三维坐标，然后使用的分而治之的办法使用飞机而不是一条线。这肯定会正常工作。可以保证这一点，因为当仅检查在球面上的点，两个最接近点通过电弧距离（距离行走在该表面上）也将是两个最接近由三维笛卡尔距离。这将有运行时间为O（nlogn）。

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).

要转换为三维坐标，最简单的方法是使（0,0,0）在地球的中心，那么你的坐标是（COS（LAT）* COS（LON），COS（LAT）*罪（LAN），罪（LAT））。为了这些目的，我使用的是规模而地球的半径为1，以简化计算。如果你希望距离在一些其他单元，只是由地球的半径时在于单元测量乘以所有的量

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.

这篇关于寻找最接近的对点上的球的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！