javascript - 根据坐标在数组中查找对象

假设我有以下格式的数组：

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

基于某些地图坐标，如何最有效地找到坐标最接近地图坐标的对象？

最佳答案

一个幼稚的解决方案是：

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

换句话说，天真的解决方案是迭代所有点，更新当前的最佳距离和相应的坐标。如果您的要点列表很小，那么这样做可能是合理的。但是，更有效的解决方案是使用树结构，其中树中的每个内部节点都由该节点下所有点的平均坐标表示。然后，通过使节点以最接近的平均坐标下降直到到达叶子来搜索树。这种方法允许您在每次迭代中抛出大量候选点，从而提供对数解。

换句话说，一个更有效的解决方案如下所示：

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

当然，这是假设您首先构建了这样的树。如果您使用相同的点集重复运行“ getClosestPoint（）”，则可能值得建立这样的结构（如果您仅对任何给定的点集执行一次“ getClosestPoint（）”，那么天真的解决方案可能是合理的）。关于K-D trees和quad trees的文章可能对于进一步阅读此通用方法以及如何将这些点建立和划分到这些树中感兴趣。

关于javascript - 根据坐标在数组中查找对象，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24239356/