Javascript - 找到离给定点最近的N个点（二维）

Question

我需要一个算法来排序一个包含大约2,500个[经度，纬度]数组的列表，以找到离给定[经度，纬度]最近的N个点。具体应用场景是寻找最近的出租车。

我已经搜索了在线资源，大多数只指向最小值。我编写了一些代码，通过forEach循环遍历列表，并计算到感兴趣点的欧几里得距离，将距离放入数组中，对其进行排序，然后提取3个最小距离，但随后我必须找到最小距离的索引，这会导致高运行时间。我还考虑过KNN，但觉得它过于复杂化了问题。

有没有更有效的方法来循环并提取3个最接近的点？例如，一些内置方法？

编辑：这里是一个例子：

感兴趣的点：[103, 1.3]

数据：

[
    [103.6632, 1.32287], [103.66506, 1.30803], [103.67088, 1.32891],
    [103.67636, 1.3354], [103.67669, 1.32779], [103.67927, 1.31477],
    [103.67927, 1.32757], [103.67958, 1.31458], [103.68508, 1.32469],
    [103.6927, 1.3386], [103.69367, 1.34], [103.69377, 1.37058],
    [103.69431, 1.37161], [103.69519, 1.35543], [103.69538, 1.34725],
    [103.6961, 1.33667], [103.696918716667, 1.35110788333333],
    [103.69731, 1.35], [103.698615333333, 1.33590666666667],
    [103.69975, 1.35], [103.70129, 1.34], [103.70247, 1.34],
    [103.70366, 1.34], [103.70394, 1.33948], [103.70403, 1.34081],
    [103.704697166667, 1.33546383333333], [103.70504, 1.34],
    [103.706281333333, 1.344646], [103.70689, 1.34464]
]

- jingwen

---

你可能想要复习一下Haversine公式。 - Patrick Roberts

谢谢。我确实注意到Haversine公式出现在一个现有的StackOverflow帖子中，但它是一种距离度量而不是算法。尽管如此，为了进行更准确的距离计算，我将切换到使用Haversine。 - jingwen

Answer 1

[...] 将距离放入数组中，进行排序，然后提取3个最小的距离，但随后必须找到这些最小距离的索引。

你可以简单地同时将索引和距离填充到该数组中。

let array = [[1, 230], [2, 222], [3, 810], [4, 125], [5, 441]];
array.sort((a, b) => a[1]-b[1]);
array.forEach(([index, distance]) => console.log(index, ':', distance));

- blakkwater

---

谢谢您的回答，您能否详细说明一下sort()如何按照到给定坐标（例如[2.5, 500]）的最近距离对数组进行排序？ - jingwen

@jingwen 这个例子展示了如何为排序准备数组。不要像 array.push(distance) 那样填充它，而是可以使用 array.push([index, distance])。这样你就可以轻松地访问原始点，以便查看你计算出的距离。 - blakkwater

我明白了...您是否知道如何将sort()函数应用于基于第一个索引的3D数组？它将按照[distance, latitude, longitude]中的距离进行排序。 - jingwen

@jingwen array.sort((a, b) => a[0]-b[0]) 将以升序排序。顺便提一下，当你想学习有关原生JavaScript的任何内容时， MDN 是你最好的朋友。 - blakkwater

Answer 2

你有

const data=[
         [103.6632, 1.32287], [103.66506, 1.30803], [103.67088, 1.32891],[103.67636, 1.3354], [103.67669, 1.32779], [103.67927, 1.31477],[103.67927, 1.32757], [103.67958, 1.31458], [103.68508, 1.32469],[103.6927, 1.3386], [103.69367, 1.34], [103.69377, 1.37058],[103.69431, 1.37161], [103.69519, 1.35543], [103.69538, 1.34725],[103.6961, 1.33667], [103.696918716667, 1.35110788333333],[103.69731, 1.35], [103.698615333333, 1.33590666666667],[103.69975, 1.35], [103.70129, 1.34], [103.70247, 1.34],[103.70366, 1.34], [103.70394, 1.33948], [103.70403, 1.34081],[103.704697166667, 1.33546383333333], [103.70504, 1.34],[103.706281333333, 1.344646], [103.70689, 1.34464]
   ]

编写距离函数（有不同的实现方式）：

function euclidian(pair1, pair2) {
  return Math.hypot(pair1[0] - pair2[0], pair1[1] - pair2[1]);
}

你有那些常量

const k=7
const point=[103, 1.3]

使用lodash实用程序库：

const _ = require('lodash')
   // .chain wraps the data to enable chaining
 _.chain(data)
  .map((row,index)=>[euclidian(row,point),index])
  .sortBy(row=>row[0])
  .slice(0,7)

结果是

[[0.6635942110205637,0],[0.6651084757391051,1],
[0.6715026154081575,2],[0.6772603932018993,4],
[0.6772857665712483,3],[0.6794305599544396,5],
[0.6797363847845737,7]]

- Yilmaz