查找数组中最近的点

Question

我不仅要查找最近点，还要查找 5 个对象点数组中的 3 个最近点。我已经尝试了几个实验，每个点只使用一个距离（d）变量。但我无法弄清楚如何遍历每个点，使用毕达哥拉斯 Theorem/Distance 公式将其与其他点进行比较，然后找到最接近的 3。如果数组有 5 个点，我猜我需要存储将每次迭代的结果放在一个具有距离 (d) 值的数组中，按距离值排序，然后删除新数组中的最后一项。这是数组：

 var points = [
   { id: 1, x: 0.0, y: 0.0 },
   { id: 2, x: 10.1, y: -10.1 },
   { id: 3, x: -12.2, y: 12.2 },
   { id: 4, x: 38.3, y: 38.3 },
   { id: 5, x: 79.0, y: 179.0 },
 ];

我有一个函数可以根据距离的 d 键值找到最近的 3 个点：

 function closest(n, { id, d }) {
    return points
      .filter(o => o.id !== id)
      .sort((a, b) => Math.abs(a.d - d) - Math.abs(b.d - d))
      .slice(0, n);
 };

而且我有办法应用此功能并在控制台记录结果，以便打印 "ID: 1stClosest, 2ndClosest, 3rdClosest":

 result = points.map(o => 
   Object.assign({}, o, { closest: closest(3, o) }));

 result.forEach((item) => {
   console.log(item.id + ': ' + item.closest[0].id + ', ' + item.closest[1].id + ', ' + item.closest[2].id);});

现在，我只是尝试遍历每个点，应用距离公式来获取每个点比较的 d: 值，将其推送到一个新数组，我假设然后应用以上部分 (result 和 closest 函数）。我怎样才能做到这一点？这是我目前所拥有的：

 points.forEach((item) => {
  var newArray = [item];
  var pt = null;
  var d = null;
  for (var i = 0; i < points.length; i = i + 1) {
      //compare this point with all of the other points
      for (var j = i + 1; j < points.length; j = j + 1) {
          //compute distance
          var curr = Math.sqrt(Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2));
      //get the distance between each point and push to a new array
          if (d === null || curr < d) {
            o = points.id[i];
            pt = points.id[j];
            d = curr;
          }
       }
     }
  newArray.push = {
   "id": o,
   "pt": pt,
   "d": d
  };
  console.log(newArray);
});

Answer 1

如果我没理解错的话，这和closest pair of points的问题类似。一种（直观但可能效率低下）的方法是简单地暴力破解集合中的项目。也就是说，对于两个点，您使用两个 for 循环。那么，对于三点，您可以使用三个嵌套循环。然后，你会找到最大值 "closeness." 我不确定你想如何定义接近度，但我认为 A 到 B、B 到 C 和 C 到 A 的距离总和会很好。测试点分组的每个枚举的最小值 "distance" 将导致最接近的配对。

所以，我不确定您的其他功能会在哪里发挥作用。更大的问题是找到如何确定 "closest," 所以调用一个函数来做一个更大的问题的子问题不会被检查出来。

如果您以某种方式想要三个最近的组点，然后您需要跟踪每个配对的距离并确定如何您想让它们彼此区分开来。也就是说，你想让同一个点出现在另一组点中吗？

查找数组中最近的点

Finding the closest points in an array

javascript

arrays

iterator

object

pythagorean