パスの距離の分数に基づいて複数のポイントを持つパスから座標を取得します

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) { 
 
\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('&'));

私が最も効率的な方法でこの問題を解決する方法についてのヘルプを探しています。ありがとうございました！

Answer 1

最初（すなわち、減算個々のエッジがオフ長）（全経路距離を乗じて）絶対距離totalDistRemainingに分数fracを変換し、その後で働いていた場合fractionCoordinateArray()の論理が多かれ少なかれ正確であろうその時点から。あなたは

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)

を渡す必要があります。

最後に、スピードを向上させるために、これまでのパスに沿った合計距離を記録する各配列要素に3番目のエントリを追加することができます（開始時には0になり、最後には合計パス長に等しい）。この値は減少しないので、バイナリ検索でO（log n）時間内の任意のパス距離を含むパスセグメントを見つけることができます。