0

我正在用 Javascript 编写一个应用程序，它使用谷歌地图并根据最近的腿计算一系列腿之间的完整路线。

假设我在地图上有 4 条腿，每条腿都有起点和终点纬度和经度。用户指定哪两条腿是路线的起点和终点。一条腿的每一端只能连接到另一条腿的起点。然后那条腿的末端连接到另一条腿的起点，依此类推。代码根据它可以找到的最近的腿来确定开始连接的腿。

例如像这样的东西（虚线是腿）：

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},
]

那些将是内腿。然后我将外部腿（两条腿是整个路线的起点和终点）存储在变量中：

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开始的地方start并让它point成为下一个start直到没有匹配并且在每一步我们将点推入result.

编辑：

这将使起点和终点的坐标重叠，但我的都没有，它们之间有很大的差距，我需要在它们之间生成“连接器”......

我通过使用一种算法来计算最近点而不是寻找重叠坐标来扩展我的第一个想法。

演示

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 实现。– @Bergi

于 2013-09-17T02:39:18.760 回答
0

我认为 DFS 可以，并将访问的有序腿列表转移到下一个递归。并在每次递归中选择最后一条腿并与每条未访问的腿递归。

于 2013-09-20T15:04:57.673 回答