JavaScript – 查找距离给定点最近的N个点（2D）

huangapple
go评论99阅读模式
英文:

Javascript - Finding the N closest points to a given point (2D)

问题

我需要一个算法来在一个包含约2,500个[经度，纬度]数组的列表中找到离给定[经度，纬度]最近的N个点。特定的用例是找到最近的出租车，用于叫车服务。

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

是否有更高效的方法来循环遍历并提取3个最近的点？例如，是否有内置方法？

编辑：这里有一个例子：

兴趣点：[103, 1.3]

数据：

  1. [
  2. 	[103.6632, 1.32287], [103.66506, 1.30803], [103.67088, 1.32891],
  3. 	[103.67636, 1.3354], [103.67669, 1.32779], [103.67927, 1.31477],
  4. 	[103.67927, 1.32757], [103.67958, 1.31458], [103.68508, 1.32469],
  5. 	[103.6927, 1.3386], [103.69367, 1.34], [103.69377, 1.37058],
  6. 	[103.69431, 1.37161], [103.69519, 1.35543], [103.69538, 1.34725],
  7. 	[103.6961, 1.33667], [103.696918716667, 1.35110788333333],
  8. 	[103.69731, 1.35], [103.698615333333, 1.33590666666667],
  9. 	[103.69975, 1.35], [103.70129, 1.34], [103.70247, 1.34],
  10. 	[103.70366, 1.34], [103.70394, 1.33948], [103.70403, 1.34081],
  11. 	[103.704697166667, 1.33546383333333], [103.70504, 1.34],
  12. 	[103.706281333333, 1.344646], [103.70689, 1.34464]
  13. ]
英文:

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:

  1. [
  2. 	[103.6632, 1.32287], [103.66506, 1.30803], [103.67088, 1.32891],
  3. 	[103.67636, 1.3354], [103.67669, 1.32779], [103.67927, 1.31477],
  4. 	[103.67927, 1.32757], [103.67958, 1.31458], [103.68508, 1.32469],
  5. 	[103.6927, 1.3386], [103.69367, 1.34], [103.69377, 1.37058],
  6. 	[103.69431, 1.37161], [103.69519, 1.35543], [103.69538, 1.34725],
  7. 	[103.6961, 1.33667], [103.696918716667, 1.35110788333333],
  8. 	[103.69731, 1.35], [103.698615333333, 1.33590666666667],
  9. 	[103.69975, 1.35], [103.70129, 1.34], [103.70247, 1.34],
  10. 	[103.70366, 1.34], [103.70394, 1.33948], [103.70403, 1.34081],
  11. 	[103.704697166667, 1.33546383333333], [103.70504, 1.34],
  12. 	[103.706281333333, 1.344646], [103.70689, 1.34464]
  13. ]

答案1

得分: 2

Here is the translated code part:

  1. let array = [[1, 230], [2, 222], [3, 810], [4, 125], [5, 441]];
  2. array.sort((a, b) => a[1]-b[1]);
  3. 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 -->

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

<!-- end snippet -->

答案2

得分: 0

Here's the translated code portion:

  1. 你有以下代码：
  3. const data = [
  4.     [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]
  5. ];
  7. 编写距离函数（有不同的实现）：
  9. function euclidian(pair1, pair2) {
  10.     return Math.hypot(pair1[0] - pair2[0], pair1[1] - pair2[1]);
  11. }
  13. 你有以下常量：
  15. const k = 7
  16. const point = [103, 1.3]
  18. 使用 [lodash][1] 实用程序库：
  20. const _ = require('lodash')
  21. // .chain 封装数据以启用链式操作
  22. _.chain(data)
  23.     .map((row, index) => [euclidian(row, point), index])
  24.     .sortBy(row => row[0])
  25.     .slice(0, 7)
  27. 结果是：
  29. [[0.6635942110205637, 0], [0.6651084757391051, 1], [0.6715026154081575, 2], [0.6772603932018993, 4], [0.6772857665712483, 3], [0.6794305599544396, 5], [0.6797363847845737, 7]]
  31. [1]: https://lodash.com/docs/4.17.15

This code portion is now translated into Chinese as requested.

英文:

you have

  1. const data=[
  2.          [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]
  3.    ]

write distance function (there are different implementations):

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

you have those constants

  1. const k=7
  2. const point=[103, 1.3]

Using lodash utilities library:

  1. const _ = require(&#39;lodash&#39;)
  2.    // .chain wraps the data to enable chaining
  3.  _.chain(data)
  4.   .map((row,index)=&gt;[euclidian(row,point),index])
  5.   .sortBy(row=&gt;row[0])
  6.   .slice(0,7)

result is

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

huangapple
  • 本文由 发表于 2023年5月22日 12:59:11
  • 转载请务必保留本文链接：https://go.coder-hub.com/76303143.html
  • algorithm
  • javascript
  • sorting
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定