Searching/Sorting Multidimensional Arrays

Question

I've created a multi-dimensional array based on the x/y coords of the perimeter of a circle. An object can be dragged along the arc (in javascript) and then 'dropped' anywhere on it. The problem is, I need to find the closest x and y coordinate to where the object is 'dropped.'

My current solution involves looping through an array and finding the closest value to x, and then looping again to find the y coordinate, but it doesn't seem very clean and there are problems with it.

Does anyone have any suggestions?

Thanks!

Answer 1

So, let's see. We assume a predefined set of (x, y) coordinates. You are given another point and have to find the nearest element of the array to that given point. I am going to assume "nearest" means the smallest Pythagorean or Euclidean distance from the given point to each of the other points.

The simplest algorithm is probably the best (if you want to look at others in Wikipedia, have at it). Since you didn't give us any code for the structure, I'm going to assume an array of objects, each object having an x and a y property, ditto for the given point.

var findNearestPoint = function (p, points) {
  var minDist = Number.POSITIVE_INFINITY,
      minPoint = -1,
      i,
      l,
      curDist,
      sqr = function(x) { return x * x; };

  for (i = 0, l = points.length; i < l; i++) {
    curDist = sqr(p.x - points[i].x) + sqr(p.y - points[i].y);
    if (curDist < minDist) {
      minDist = curDist;
      minPoint = i;
    }
  } 
  return points[i];
};

(Untested, but you get the idea.)