在数组中找到最接近的点 [英] Finding the closest points in an array

问题描述

我试图不仅在5个对象点的数组中找到最接近的点，而且在3个最接近的点.我已经尝试过对每个点仅使用distance(d)变量进行多次实验.但是我无法弄清楚如何迭代每个点，使用勾股定理/距离公式将其与其他点进行比较，然后找到最接近的3.如果数组有5个点，我想我需要存储的结果具有距离(d)值的数组中的每个迭代，按距离值排序，然后删除新数组中的最后一项.这是数组:

I am trying to find not just the closest point, but the 3 closest points in an array of 5 object points. I have tried several experiments using just a distance(d) variable for each point. But I cannot figure out how to iterate through each point, compare it to the other points using the Pythagorean Theorem/Distance formula, and then find the closest 3. If the array has 5 points, I am guessing I need to store the results of each iteration in an array with a distance (d) value, sort by the distance value, and then remove the last item in the new array. Here is the array:

 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个点:

I have a function that finds the closest 3 points based on a d key value for distance:

 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":

And I have a way to apply this function and console log the results so that it prints "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功能).我怎样才能做到这一点?这是我到目前为止的内容:

Now, I am just trying to iterate through each point, apply the distance formula to get the d: value for each point comparison, push it to a new array, I assume and then apply the above portions (result and closest functions). How can I do this? Here's what I have so far:

 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);
});

推荐答案

如果我正确理解，则类似于

If I understand correctly, this is similar to the closest pair of points problem. One (intuitive, but perhaps inefficient) approach is to simply brute force the items in the collection. That is, for two points, you use two for loops. For three points, then, you could use three nested loops. Then, you'd find the maximum "closeness." I'm not sure how you want to define closeness, but I figure the sum of the distances from A to B, B to C, and C to A would work well. Testing every enumeration of the point groupings for minimum "distance" would result in the closest pairing.

因此，我不确定您的其他功能将在哪里发挥作用.更大的问题是找到如何确定最接近"的问题，因此调用函数来处理更大问题的子问题不会解决.

So, I'm not sure where your other functions would come into play. The larger problem is finding how to determine "closest," so calling a function to do a subproblem that is the bigger problem doesn't check out.

如果您以某种方式想要三个最接近的组点， then ，则需要跟踪每个配对的距离并确定如何使它们与每个配对保持不同其他.即是否要允许同一点出现在另一组点中?

If you somehow want the three closest groups of points, then you would need to keep track of each pairing's distance and determine how your want to keep them distinct from each other. I.e., do you want to allow the same point to be in another group of points?

这篇关于在数组中找到最接近的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！