有谁能建议一个有效的算法来解决这个问题？我在Ruby中实现这个,所以如果有一个合适的库那么就知道了,但我仍然对算法感兴趣！
更新：有几个人要求提供有关问题的更多具体细节.所以这里是：
> 5000点大多在同一个城市内.它外面可能有一些,但可以安全地假设它们中的99％位于半径75公里范围内,并且所有这些都在半径200公里范围内.
>点数列表很少变化.为了争论,让我们说它每天更新一次,我们必须在那个时候处理几千个请求.
解决方法
考虑这相当于拒绝球形矩形边界框外的任何东西(作为圆形边界框的近似值).
我不做Ruby所以这里是伪代码算法：
让你的参考点P(pa,po)的纬度,经度和另一个点X(xa,xo).
预计算ka,纵向距离的纬度比例因子：ka(= cos(pa in°)). (严格地说,ka =常数是P附近的线性化近似)
然后距离估计器是：D(X,P)= ka * | xa-pa | | XO-PO | = ka * da do
其中| z |表示abs(z).在最坏的情况下,这会高估真实距离√2(当da == do时),因此我们允许如下：
做一个正在运行的搜索并保持Dmin,这是第五小的缩放曼哈顿距离估计.
因此,您可以预先拒绝D(X,P)> D的所有点. √2* Dmin(因为它们必须至少比√((ka * da)²do²更远) – 这应该消除99.9％的点数).
保留所有剩余候选点的列表,其中D(X,P)<=√2* Dmin.如果找到新的第五小的D.优先级队列,则更新Dmin,否则(coord,D)列表是良好的数据结构.
请注意,我们从未计算过欧几里德距离,我们只使用了浮点乘法和加法.
(考虑到这类似于四叉树,除了过滤除了我们感兴趣的区域之外的所有内容,因此无需预先计算准确的距离或构建数据结构.)
如果你告诉我们纬度,经度(度数,分钟或者什么？)的预期扩散会有所帮助？如果所有点都接近,那么估算器中的√2因子将过于保守并将每个点标记为候选者;查找 – 基于表格的距离估计器将是更可取的.)
伪代码：
initialize Dmin with the fifth-smallest D from the first five points in list
for point X in list:
if D(X,P) <= √2 * Dmin:
insert the tuple (X,D) in the priority-queue of candidates
if (Dmin>D): Dmin = D
# after first pass,reject candidates with D > √2 * Dmin (use the final value of Dmin)
# ...
# then a second pass on candidates to find lowest 5 exact distances