0

Google マップを使用し、最も近い区間に基づいて一連の区間間の完全なルートを計算する Javascript でアプリを作成しています。

マップ上に 4 つの区間があるとします。各区間には開始点と終了点の緯度と経度があります。ユーザーは、ルートの始点と終点となる 2 つのレグを指定します。脚の各端は、別の脚の開始点にのみ接続できます。次に、その脚の終点が別の脚の始点に接続されます。コードは、検出できる最も近いレッグに基づいて、接続を開始するレッグを決定します。

たとえば、次のようなものです（破線は脚です）：

start-----------end  <-connector->  start----------end  <-connector->  start----------end

すべての脚の座標の配列を取得しました。この配列を並べ替えて、適切な接続の進行に従うようにしたいと考えています。次に、配列を使用して、配列を直線的にループすることでコネクタを生成できます。

配列は次のようになります。

[
   {start_lat: X, start_lng: X, end_lat: X, end_lng: X},
   {start_lat: X, start_lng: X, end_lat: X, end_lng: X},
]

それが内脚になります。そして、外側の区間 (ルート全体の始点と終点である 2 つの区間) を変数に格納します。

var start = {end_lat: X, end_lng: X}
var end = {start_lat: X, start_lng: X}

例として、次のような結果になる可能性があります。

start -> array[0] -> array[1] -> end

または、次のようになる可能性があります。

start -> array[1] -> array[0] -> end

アルゴリズムは、開始レグ end_lat,end_lng と終了レグ end_lat,end_lng に基づいて配列をソートする必要があります。

最終結果は、最短経路で接続された大きなルートになります。

これらの固有の要因を考慮に入れたソート アルゴリズムを記述する方法を考えるのに苦労しています。

これを言葉で表現するのは難しく、どうすればわかりやすくできるかわかりませんが、追加するのに役立つ何かが思いついたら、この投稿を編集します. ありがとう。

編集：

これが私が話していることの写真です：

地図

黒い線は脚です。赤い線は、脚の座標の配列を正しい順序に並べ替えた後に生成する必要があるコネクタです。コネクタの生成はこのアルゴリズムの一部ではありませんが、全体像を理解できるように、これは私が達成しようとしていることの単なる例です。ご覧のとおり、脚の間に隙間があり、どの座標も重なっていません。

4

2 に答える 2

2

次のようなことができます。

デモ

var start = { end_lat: 1, end_lng: 1 },
    end = { start_lat: 4, start_lng: 4 },
    coordsBetween = [
        { start_lat: 2, start_lng: 2, end_lat: 3, end_lng: 3  },
        { start_lat: 1, start_lng: 1, end_lat: 2, end_lng: 2  },
        { start_lat: 3, start_lng: 3, end_lat: 4, end_lng: 4  }
    ];

function orderedCoords(start, coords) {
    var result = [],
        point = start;

    while (point = coords.filter(function (item) {
        return item.start_lat === point.end_lat
        && item.start_lng === point.end_lng;
    })[0]) {
        result.push(point);
    }   
    return result;
}

console.log(orderedCoords(start, coordsBetween));

基本的には、終了pointするところから始まる次のものを見つけ、一致するものがなくなるまでそれを次のものにし、各ステップでポイントを に押し込みます。startpointstartresult

編集：

これは、開始点と終了点の座標が重なっている場合に機能しますが、私のものはどれも機能しません。それらの間に大きなギャップがあり、それらの間に「コネクタ」を生成する必要があります...

重複する座標を探すのではなく、アルゴリズムを使用して最も近い点を計算することで、最初のアイデアを拡張しました。

デモ

var start = { end_lat: 1, end_lng: 1 },
    end = { start_lat: 4, start_lng: 4 },
    segments = [
        { start_lat: 2, start_lng: 2, end_lat: 3, end_lng: 3  },
        { start_lat: 1, start_lng: 1, end_lat: 2, end_lng: 2  },
        { start_lat: 3, start_lng: 3, end_lat: 4, end_lng: 4  }
    ];

function orderedSegments(start, segments) {
    var result = [],
        segment = start,
        i;

    while ((i = indexOfClosestSegment(segment, segments)) !== -1) {
        result.push(segment = segments.splice(i, 1)[0]);
    }

    return result;
}

function indexOfClosestSegment(segment, segments) {
    var i = 0,
        len = segments.length,
        segIndex = -1,
        tempDistance, smallestDistance;

    for (; i < len; i++) {
        if (
            (tempDistance = distanceBetween(segment, segments[i])) < smallestDistance 
            || typeof smallestDistance === 'undefined') {
            smallestDistance = tempDistance;
            segIndex = i;
        }
    }

    return segIndex;        
}

function distanceBetween(segmentA, segmentB) {
    return Math.sqrt(
        Math.pow(segmentB.start_lat - segmentA.end_lat, 2) 
        + Math.pow(segmentB.start_lng - segmentA.end_lng, 2)
    );
}

console.log(orderedSegments(start, segments));

ポイントは地理座標であり、自明なピタゴラスではなく、球面距離アルゴリズムを使用する必要があることに注意してください。GM は、データ構造に対してそのようなヘルパー関数を提供していると思います。もちろん、アルゴリズムは別の distanceBetween 実装でも機能します。– @ベルギ

于 2013-09-17T02:39:18.760 に答える