Find object in array based on coordinates

Question

Say I have an array in this format:

var arr = [{lat: 123.123, lng: 321.321}, {lat: 567.567, lng: 765.765}]

Based on some map coordinates, how can I most effectively find the object with coordinates closest to the map coordinates?

Answer 1

A naive solution is to do:

var getClosestPoint = function(coord, coordArray) {
  var bestDistance = null;
  var bestCoord = null;
  for (var i = 0; i < coordArray.length; ++i) {
    var currentCoord = coordArray[i];
    var distance = getDistance(coord, currentCoord);
    if ((bestDistance == null) || (distance < bestDistance)) {
      bestDistance = distance;
      bestCoord = currentCoord;
    }
  }
  return {'distance': bestDistance, 'coord':bestCoord};
 };

 // Based on the solution here:
 // http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates
 var getDistance = function(coordA, coordB) {
   var R = 6371; // km
   var dLat = (coordB.lat-coordA.lat).toRad();
   var dLon = (coordB.lng-coordA.lng).toRad();
   var lat1 = coordA.lat.toRad();
   var lat2 = coordB.lat.toRad();

   var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
           Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2); 
   var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
   var d = R * c;
   return d;
 };

In other words, the naive solution is to just iterate through all the points, updating the current best distance and the corresponding coordinate. If your list of points is small, this may be reasonable to do. However, a more effective solution is to use a tree structure, where each internal node in the tree is represented by the mean coordinate of all points under that node. You then search the tree by descending the node with the closest mean coordinate until you reach a leaf. This approach allows you to throw out a larger number of candidate points in each iteration, giving a logarithmic solution.

In other words, a more effective solution looks like:

var getClosestPoint = function(coord, coordNode) {
  var children = coordNode.getChildren();
  if (children.length == 0) {
    return coordNode.getCenterCoord();
  }

  var closestChild = null;
  var bestDistance = 0.0;
  for (var i = 0; i < children.length; ++i) {
    var currentCoord = children[i].getCenterCoord();
    var distance = getDistance(coord, currentCoord);
    if ((closestChild == null) || (distance < bestDistance)) {
      closestChild = children[i];
      bestDistance = distance;
    }
  }
  return getClosestPoint(coord, closestChild);
}

Of course, this assumes that you've built up such a tree in the first place. If you are running "getClosestPoint()" repeatedly with the same set of points, then it is probably worthwhile to build up such a structure (if you only execute "getClosestPoint()" once for any given set of points, then the naive solution may be reasonable). The articles on K-D trees and quad trees may be of interest for further reading on this general approach and how to build up and partition the points into these trees.

Answer 2

I believe this should work on a square grid. If the values reset after a certain point, like on earth, there needs to be some adjustment to this solution.

function calculateDistance(x1, x2, y1, y2){
  return Math.sqrt(Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2));
}

var retrievedCoords = {lat: 12234, lng: 135};
var closestPoint = arr[0];
var distanceToClosestPoint = calculateDistance(retrievedCoords.lat, arr[0].lat, retrievedCoords.lng, arr[0].lng);

for (var i = 1; i < arr.length; i++){
  var tempDist = calculateDistance(retrievedCoords.lat, arr[i].lat, retrievedCoords.lng, arr[i].lng);
  if (tempDist > distanceToClosestPoint){
    closestPoint = arr[i];
    distanceToClosestPoint = tempDist;
  }
}