ruby – 最近点的算法

你可以使用曼哈顿距离(按纬度缩放)获得一个非常快速的上限估计量,这应该足以拒绝99.9％的候选人,如果他们不接近(编辑：那时你告诉我们他们很接近.在这种情况下,您的指标应该是距离平方,根据Lars H评论).
考虑这相当于拒绝球形矩形边界框外的任何东西(作为圆形边界框的近似值).
我不做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)2do2更远) – 这应该消除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