英文:
Javascript - Finding the N closest points to a given point (2D)
问题
我需要一个算法来在一个包含约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]
]
英文:
I need an algorithm to sort through a list of ~2,500 [longitude, latitude] arrays to find the N closest points to a given [longitude, latitude]. The particular use case is finding the closest taxis for ride hailing
I have searched through online resources and most of them point toward only the minimum value. I have wrote some code where I looped through the list via a forEach and calculated the Euclidean distance to the point of interest, placed the distances into an array, sorted it, then extracted the 3 smallest distances, but then I had to find the indexes of the smallest distances, which leads to a high runtime. I also considered KNN but felt it was overcomplicating the problem
Is there a more efficient way to loop through and extract the 3 closest points? For example, some built-in method?
Edit: Here's an example:
Point of interest: [103, 1.3]
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]
]
答案1
得分: 2
Here is the translated code part:
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));
If you need further assistance or have more code to translate, please let me know.
英文:
> [...] placed the distances into an array, sorted it, then extracted the 3 smallest distances, but then I had to find the indexes of the smallest distances
You can simply populate that array with both indices and distances at the same time.
<!-- begin snippet: js hide: false console: true babel: false -->
<!-- language: lang-js -->
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));
<!-- end snippet -->
答案2
得分: 0
Here's the translated code portion:
你有以下代码：
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][1] 实用程序库：
const _ = require('lodash')
// .chain 封装数据以启用链式操作
_.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]]
[1]: https://lodash.com/docs/4.17.15
This code portion is now translated into Chinese as requested.
英文:
you have
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]
]
write distance function (there are different implementations):
function euclidian(pair1, pair2) {
return Math.hypot(pair1[0] - pair2[0], pair1[1] - pair2[1]);
}
you have those constants
const k=7
const point=[103, 1.3]
Using lodash utilities library:
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)
result is
[[0.6635942110205637,0],[0.6651084757391051,1],
[0.6715026154081575,2],[0.6772603932018993,4],
[0.6772857665712483,3],[0.6794305599544396,5],
[0.6797363847845737,7]]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论