Var*_*rma 6 algorithm points latitude-longitude closest
我知道如何为2D情况(x和y)实现n log n最接近的点算法(Shamos和Hoey).然而,对于给出纬度和经度的问题,不能使用这种方法.使用半正弦公式计算两点之间的距离.
我想知道是否有某种方法可以将这些纬度和经度转换为它们各自的x和y坐标并找到最接近的点对,或者是否有其他技术可以用来做它.
Kei*_*win 12
我会将它们转换为三维坐标,然后使用平面而不是直线来使用分而治之的方法.这肯定会正常工作.我们可以确定这一点,因为当仅检查球体上的点时,两个最接近点的弧距(在表面上行走的距离)也将是最接近三维笛卡尔距离的两个点.这将有运行时间O(nlogn).
要转换为三维坐标,最简单的方法是使(0,0,0)成为地球的中心,然后你的坐标是(cos(lat)*cos(lon),cos(lat)*sin(lan) ),罪(LAT)).出于这些目的,我使用的是地球半径为1的比例,以简化计算.如果您想在某个其他单位中建立距离,只需将所有数量乘以在该单位中测量的地球半径即可.
我应该注意到,所有这些都假设地球是一个球体.它不完全是一个,点也可能实际上具有高度,因此这些答案实际上并不完全准确,但几乎在每种情况下它们都非常接近正确.
| 归档时间： |
|
| 查看次数： |
2201 次 |
| 最近记录： |