Obtenir la coordonnée à partir du chemin avec plusieurs points en fonction de la fraction de la distance du chemin

Question

J'ai un tableau où chaque valeur de tableau est un objet { lat: ___, lng: ___ }. Je voudrais entrer une fraction (disons 20% (0.2)) et obtenir la coordonnée spécifique pour cette fraction, basée sur la distance du point 0. Qu'est-ce que cela signifie que étant donné la distance d (somme de tous les chemins individuels entre les points) , la coordonnée devrait être 1/5 de d. Si je devais mettre la fraction à 0 cela me donnerait les premières coordonnées dans le chemin. Et si je devais mettre la fraction à 1 ça me donnerait le dernier.

J'ai lu sur les coordonnées basées sur les fractions ici sur SO (Calculate point between two coordinates based on a percentage) et utilisé cette fonction dans mon algorithme.

Ce que j'ai pensé que je pourrais faire est d'ajouter tous les chemins entre chaque point pour obtenir une somme d. Ensuite, pour chaque distance entre les points f je vérifie pour voir si cette distance était inférieure à d. Si true, déduire f de d. Si false, utilisez la fonction du lien ci-dessus et entrez la fraction restante d. Je pensais que cela me donnerait la bonne coordonnée.

Cela fonctionne dans une certaine mesure, mais pour les chemins individuels avec une longue distance, il laisse des lacunes tout au long du chemin complet.

Voici le code de l'algorithme ainsi que le code de génération de cette image. Je pense que le problème se produit dans modules.fractionCoordinateArray.

var modules = {}; 
 

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

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

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

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

 
\t return total; 
 
}; 
 

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

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

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

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

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

 

 
/* 
 
\t 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++) { 
 
\t var crd = modules.fractionCoordinateArray(path, i/50); 
 
\t 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('&'));

Je suis à la recherche de l'aide sur la façon de résoudre ce problème de la manière la plus efficace. Je vous remercie!

Answer 1

La logique en fractionCoordinateArray() serait plus ou moins correct si vous d'abord converti la fraction frac dans une distance absolue totalDistRemaining (en le multipliant par la distance totale du trajet), puis travaillé avec (à savoir, soustrait bord individuel longueurs off) à partir de ce moment-là.

Ensuite, lorsque vous appelez

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

vous devriez plutôt passer

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

comme le dernier paramètre. Enfin, pour améliorer la vitesse, vous pouvez ajouter une troisième entrée à chaque élément du tableau qui enregistre la distance totale le long du chemin jusqu'à présent (donc ce sera 0 au début, et égal à la longueur totale du chemin à la fin). Ces valeurs seront non décroissantes, de sorte que vous pouvez maintenant trouver le segment de chemin contenant une distance de chemin donné en temps O (log n) avec une recherche binaire.