javascript - 根据路径距离的分数从具有多个点的路径获取坐标

Question

我有一个数组，其中每个数组值都是一个对象 { lat: ___, lng: ___ } 。我想输入一个分数(比如 20% (0.2))并根据与点 0 的距离获取该分数的特定坐标。这是什么表示给定距离 d(点之间所有单独路径的总和)，坐标应为 d 的 1/5。如果我将分数设置为 0，这将给我路径中的第一个坐标。如果我将分数设置为 1，它会给我最后一个。

我已经在 SO ( Calculate point between two coordinates based on a percentage ) 上阅读了基于分数的坐标，并在我的算法中使用了这个函数。

我想我可能会做的是将每个点之间的所有路径加在一起以获得总和 d。然后对于点 f 之间的每个距离，我会检查该距离是否小于 d。如果 true，从 d 中减去 f。如果 false，使用上面链接中的函数并输入剩余的分数 d。我以为这会给我正确的坐标。

这在一定程度上可行，但对于距离较长的个人路径，它会在整个路径中留下间隙。

这是算法的代码以及生成这张图片的代码。我认为问题出现在 modules.fractionCoordinateArray 中。

var modules = {};

modules.distance = function(lat1, lon1, lat2, lon2, km = true) {
  var p = 0.017453292519943295,
    c = Math.cos;
  var a = 0.5 - c((lat2 - lat1) * p) / 2 + c(lat1 * p) * c(lat2 * p) * (1 - c((lon2 - lon1) * p)) / 2;

  if (km) {
    return 12742 * Math.asin(Math.sqrt(a)); // 2 * R; R = 6371 km
  } else {
    return 12742 * Math.asin(Math.sqrt(a)) * 1000; // meters
  }
};

modules.distanceSum = function(arr, km = true) {
  var total = 0;

  for (var i = 0; i < arr.length; i++) {
    if (i > 0) {
      total += modules.distance(arr[i - 1].lat, arr[i - 1].lng, arr[i].lat, arr[i].lng, km);
    }
  }

  return total;
};

modules.fractionCoordinateArray = function(arr, frac = 0) {
  var dist = modules.distanceSum(arr),
    fractions = [];

  if (frac <= 0) {
    return {
      lat: arr[0].lat,
      lng: arr[0].lng
    };
  } else if (frac >= 1) {
    return {
      lat: arr[arr.length - 1].lat,
      lng: arr[arr.length - 1].lng
    };
  }

  for (var i = 0; i < arr.length; i++) {
    if (i > 0) {
      var frc = modules.distance(arr[i - 1].lat, arr[i - 1].lng, arr[i].lat, arr[i].lng) / dist;

      if (frac > frc) {
        frac -= frc;
      } else {
        return modules.fractionCoordinate(arr[i - 1].lat, arr[i - 1].lng, arr[i].lat, arr[i].lng, frac);
      }
    }
  }
};

modules.fractionCoordinate = function(lat1, lng1, lat2, lng2, per) {
  return {
    lat: lat1 + (lat2 - lat1) * per,
    lng: lng1 + (lng2 - lng1) * per
  };
};

/*
	For generating the image I used this;
*/
var dst = [],
  path = [{
    lat: 12,
    lng: 12
  }, {
    lat: 13.75,
    lng: 13
  }, {
    lat: 14,
    lng: 17
  }, {
    lat: 59,
    lng: 18
  }]; // Example path
  
for (var i = 0; i < 51; i++) {
  var crd = modules.fractionCoordinateArray(path, i / 50);
  dst.push('markers=size:tiny%7C' + crd.lat + ',' + crd.lng);
}
console.log('https://maps.googleapis.com/maps/api/staticmap?autoscale=2&size=600x300&maptype=roadmap&format=png&visual_refresh=true&' + dst.join('&'));

我正在寻求有关如何以最有效的方式解决此问题的帮助。谢谢!

Answer 1

如果您首先将分数 frac 转换为绝对距离 totalDistRemaining(通过将其乘以总路径距离)，然后从该点开始计算(即减去各个边的长度)。

然后当你打电话

return modules.fractionCoordinate(arr[i-1].lat, arr[i-1].lng, arr[i].lat, arr[i].lng, frac);

你应该通过

totalDistRemaining/distance(arr[i-1].lat, arr[i-1].lng, arr[i].lat, arr[i].lng)

作为最后一个参数。

最后，为了提高速度，您可以向每个数组元素添加第三个条目，记录到目前为止沿路径的总距离(因此开始时为 0，最后等于路径总长度) .该值将不会递减，因此您现在可以使用二分查找在 O(log n) 时间内找到包含任何给定路径距离的路径段。