algorithm - map API : Finding the longest common path in two given paths

Question

Google map 和 Bing map 具有可以给出 map 上从 A 点到 B 点的方向的方法。这会在 map 上突出显示从 A 到 B 的路径 - 将此称为 P1假设，P2是从C到D的另一条路径(其他一些点)，我们如何找到路径P1和P2之间最长的公共(public)路径长度？

Answer 1

你有很多方法可以做你想做的事。奇怪的是，我尝试只使用 JavaScript 来做到这一点，为此，我使用了 JSTS 库来计算两条路线之间的交点(在我的例子中，几何是从 Bing 检索的，但我没有在这个例子中包含请求作为这没有帮助)。

用例:

所以，你想要两条路径之间的公共(public)路径(或者你可以使用汽车共享或你可以与你的 friend 运行的路线部分)，如果这是正确的，那么这个例子将帮助你。

图书馆:

首先需要以下库:JSTS，可以通过Github专用仓库获取:https://github.com/bjornharrtell/jsts

其他有趣的库是 Turf，可在此处获取:https://github.com/Turfjs/

使用 JSTS 和传单实现:

在这种情况下，这是一段有趣的 JavaScript:

<script type="text/javascript">
var routeCoordinatesA = [[50.619512, 3.061242]....TRUNCATED FOR READIBILITY** ];
var routeCoordinatesB = [[50.619512, 3.061242]....TRUNCATED FOR READIBILITY** ];

$(function () {
    var map = L.map('map').setView([47.5, 2.75], 5);

    // Add base tile layer - sample from Leaflet website
    L.tileLayer('http://{s}.tile.thunderforest.com/transport/{z}/{x}/{y}.png', {
        attribution: '&copy; <a href="http://osm.org/copyright">OpenStreetMap</a> contributors'
    }).addTo(map);

    var polylineA = L.polyline(routeCoordinatesA, { color: '#4b98dc' }).addTo(map);
    var polylineB = L.polyline(routeCoordinatesB, { color: '#de6262' }).addTo(map);

    var geometryFactory = new jsts.geom.GeometryFactory();

    // Coordinates adapted to match for jsts
    var coordsA = [];
    $.each(routeCoordinatesA, function (idx, current) { coordsA.push([current[1], current[0]]); });

    var coordsB = [];
    $.each(routeCoordinatesB, function (idx, current) { coordsB.push([current[1], current[0]]); });

    // Element A
    var coordinatesA = bindCoord2JTS(coordsA);
    var shellA = geometryFactory.createLinearRing(coordinatesA);
    var jstsPolygonA = geometryFactory.createPolygon(shellA);

    // Element b
    var coordinatesB = bindCoord2JTS(coordsB);
    var shellB = geometryFactory.createLinearRing(coordinatesB);
    var jstsPolygonB = geometryFactory.createPolygon(shellB);

    // Interection
    var bufferTolerance = (2 / 1000);   // Small buffer to avoid different node no detection
    var intersection = shellA.buffer(bufferTolerance).intersection(shellB);  

    var intersectionPoints = [];
    $.each(intersection.getCoordinates(), function (idx, current) {
        intersectionPoints.push([current.x, current.y]);
    });
    intersectionPoints.pop();
    var intersectionLine = L.polyline(intersectionPoints, { color: '#4fc281', weight: 8 }).addTo(map);

    map.fitBounds(routeCoordinatesA.concat(routeCoordinatesB));
});


var bindCoord2JTS = function (coords) {
    var coordinates = [];
    for (var i = 0; i < coords.length; i++) {
        coordinates.push(new jsts.geom.Coordinate(
            coords[i][1], coords[i][0]));
    }
    return coordinates;
};

您也可以在 Github 上获取我的 Leaflet 实验中的所有工作示例: https://github.com/nicoboo/maps/tree/master

这里是实现我所说内容的页面: https://github.com/nicoboo/maps/blob/master/Boo.Maps.Web.LeafletExperiments/LeafletWithin/index.html

现场演示:http://htmlpreview.github.io/?https://github.com/nicoboo/maps/blob/master/Boo.Maps.Web.LeafletExperiments/LeafletWithin/index.html

注意事项:

当然，这实际上是基于客户端的，在服务器端获取信息可能会有用，我建议使用支持空间的数据库，这样您就可以使用 STBuffer() 和 STIntersection()直接在列上的方法或您以最佳性能操作的结果。