通过经纬度高效获取位置信息


问题描述:
有一堆数据,每一条数据由平面坐标构成, 即P(x, y), 有几千万个这样的点. 现在输入一个点D(x, y),请从上面一堆数据中找出离这个点距离最近的点.

要求:
运算速度快, 精确

算法

一起画圆圈 12 years ago

可以这样做:
以这个点为圆心,初始化1为半径,画圆,如果园内包含其他点且不止一个,则将半径缩减一半,继续判断。如果园内不包含点,则将半径增大0.5倍,继续判断。这样最终能够找到一个点,该点在圆内,其他点都在圆外。那么这个点就是距离最近的点。
其实上述半径的变化可以参照TCP中防止拥塞机制中发包时间间隔来进行合理变化,或者参考初始大变化,接近解的时候变化越来越小的方法。

我不是毛毛 answered 12 years ago

Your Answer