Get coordinate from path with multiple points based on fraction of path's distance

Question

I have an array where every array value is an object { lat: ___, lng: ___ }. I'd like to input a fraction (let's say 20% (0.2)) and get the specific coordinate for that fraction, based on the distance from point 0. What this means that given the distance d (sum of all individual paths between points), the coordinate should be 1/5 of d. If I were to set the fraction to 0 this would give me the first coordinates in the path. And if I were to set the fraction to 1 it'd give me the last.

I've read up on coordinates based on fractions here on SO (Calculate point between two coordinates based on a percentage) and used this function in my algorithm.

What I figured I might do is add all paths between each point together to get a sum d. Then for every distance between points f I'd check to see if this distance were lower than d. If true, deduct f from d. If false, use the function from the link above and input the remaining fraction d. I thought this'd give me the correct coordinate.

This works to some extent but for individuals paths with a long distance it leaves gaps throughout the full path.

Here's the code for the algorithm as well as the code for generating this picture. I think the problem occurs in 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('&'));

I'm looking for help on how to solve this problem in the most efficient way. Thank you!

Answer 1

The logic in fractionCoordinateArray() would be more or less correct if you first converted the fraction frac into an absolute distance totalDistRemaining (by multiplying it by the total path distance), and then worked with (i.e., subtracted individual edge lengths off) that from that point on.

Then when you call

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

you should instead pass

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

as the last parameter.

Finally, to improve speed, you could add a third entry to each array element that records the total distance along the path so far (so this will be 0 at the start, and equal to the total path length at the end). This values will be nondecreasing, so you can now find the path segment containing any given path distance in O(log n) time with binary search.