Comparing the distance between multiple points

Question

I am trying to apply the Pythagorean Theorem to find the distance between an array of points as I iterate through the array and then spit out the n number of closest points. I am confused as to how I get the d: distance between the iterated point and the next point to compare to the distance of the iterated point and the next +1 point after that and so forth. I start with my array of points:

 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 },
 ];

I then want to iterate over them and make a new array for each point of the distance between it and the other points using the Pythagorean theorem:

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

It seems like I have some area of the logic incorrect here and I keep getting random Cannot read property '0' of undefined errors whenever I try variation. Any suggestions on what I am doing incorrect?

CertainPerformance CertainPerformance · Accepted Answer · 2018-06-15T20:54:50

You're iterating over each item three times currently: you have a forEach with a nested for with another nested for. You're also trying to do math on points[i][0] and points[j][0] etc, but those do not exist - points[j], for example, is an object with x and y properties, not an array with numeric indicies.

It'll be a lot clearer if you give each separate point a variable, and use the exponentiation operator:

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 },
];

const pointPairs = [];
for (let i = 0; i < points.length; i = i + 1) {
  const p1 = points[i];
  for (let j = i + 1; j < points.length; j = j + 1) {
    const p2 = points[j];
    const distance = Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
    pointPairs.push({ p1: p1.id, p2: p2.id, distance });
  }
}
pointPairs.sort((a, b) => a.distance - b.distance);
console.log(pointPairs.slice(0, 5));

Or, it's even cleaner if you use array methods instead:

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 },
];

const pointPairs = [];
points.forEach((p1, i) => {
  points.slice(i + 1).forEach(p2 => {
    const distance = Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
    pointPairs.push({ p1: p1.id, p2: p2.id, distance });
  });
});
pointPairs.sort((a, b) => a.distance - b.distance);
console.log(pointPairs.slice(0, 5));

Comparing the distance between multiple points

1 Answers