Как рассчитать расстояние между двумя точками вдоль пути?

Question

Я использую openlayers3, и у меня есть закодированная геометрия. Я могу получить координаты (lat, lng) для всех точек пути (около 500 точек на каждый путь). Учитывая случайную точку внутри пути, как мне рассчитать расстояние между началом пути до этой точки?

Я взглянул на turfjs, и это выглядит очень многообещающе, но решение, которое я изобразил с его помощью, было бы не очень приятным. Принимая случайную точку (p1), я мог бы обнаружить точку (p2) пути, которая ближе всего к p1, затем сгенерировать новый многоугольник и вычислить его полное расстояние. У него могут быть проблемы с производительностью, хотя поиск будет O (log n) и новый многоугольник O (n).

EDIT: случайная точка не обязательно находится внутри пути, это координата GPS, и есть запас для ошибки.

EDIT 2: оценка по числу точек был выключен, каждый путь имеет около 500 точек, а не 5k

Кто-нибудь знает лучшего подхода? Я не очень опытен ни с openlayers3, ни с turfjs.

Answer 1

Как вы упомянули, что вы используете OpenLayers 3, я сделал пример использования OpenLayers 3, идея:

1. Получить Closest Point across the LineString дал координатная

2. перебрать LineString точек Вычисляя расстояние каждого отдельного пути и посмотреть, пересечет ли наш ближайший пункт отдельный путь.

/* Let's Generate a Random LineString */ 
 

 
var length = 5000; 
 

 
var minLongitude = Math.random()*-180 + 180; 
 

 
var minLatitude = Math.random()*-90 + 90; 
 

 
var wgs84Sphere = new ol.Sphere(6378137); 
 

 
var lastPoint = [minLongitude, minLatitude] 
 

 
var points = Array.from({ length }) 
 
.map(_ =>{ 
 
    var newPoint = [ 
 
    Math.random() * (Math.random() > 0.8 ? -.005 : .005) + lastPoint[0] 
 
    , Math.random() * (Math.random() > 0.2 ? -.005 : .005) + lastPoint[1] 
 
    ] 
 
    lastPoint = newPoint; 
 
    return newPoint; 
 
}) 
 

 
var distanceTotal = points 
 
.reduce((dis, p, i)=>{ 
 
    if(points[i + 1]) 
 
    dis += wgs84Sphere.haversineDistance(p, points[i + 1]) 
 
    return dis;   
 
}, 0); 
 

 
console.log(distanceTotal) 
 

 
var extent = new ol.extent.boundingExtent(points) 
 

 
//console.log(points) 
 

 
var lineString = new ol.Feature({ 
 
    geometry : new ol.geom.LineString(points) 
 
}); 
 

 
var source = new ol.source.Vector(); 
 

 
var layer = new ol.layer.Vector({ source }); 
 

 
source.addFeature(lineString); 
 

 

 
var map = new ol.Map({ 
 
    layers: [ 
 
    new ol.layer.Tile({ 
 
     source: new ol.source.OSM() 
 
    }) 
 
    ], 
 
    target: 'map', 
 
    controls: ol.control.defaults({ 
 
    attributionOptions: /** @type {olx.control.AttributionOptions} */ ({ 
 
     collapsible: false 
 
    }) 
 
    }), 
 
    view: new ol.View({ 
 
    projection : 'EPSG:4326', 
 
    center: [0, 0], 
 
    zoom: 2 
 
    }) 
 
}); 
 

 
map.addLayer(layer) 
 
map.getView().fit(extent, map.getSize()) 
 

 
var auxLayer = new ol.layer.Vector({ source : new ol.source.Vector() }) 
 

 
var styleAux = new ol.style.Style({ 
 
    stroke: new ol.style.Stroke({ 
 
    color: 'green', 
 
    width: 2 
 
    }) 
 
}); 
 

 
var styleAuxLine = new ol.style.Style({ 
 
    stroke: new ol.style.Stroke({ 
 
    color: 'green', 
 
    width: 0.5 
 
    }) 
 
}); 
 

 
var styleAuxPoint = new ol.style.Style({ 
 
    image : new ol.style.Circle({ 
 
    radius: 5, 
 
    fill: null, 
 
    stroke: new ol.style.Stroke({color: 'black', width: 2}) 
 
    }) 
 
}); 
 

 
var styleAuxSourcePoint = new ol.style.Style({ 
 
    image : new ol.style.Circle({ 
 
    radius: 3, 
 
    fill: null, 
 
    stroke: new ol.style.Stroke({color: '#00bbff', width: 0.5}) 
 
    }) 
 
}); 
 

 
auxLayer.setStyle(function(f, r){ 
 
    var type = f.getGeometry().getType(); 
 
    if(type === 'LineString') return styleAux; 
 
    return styleAuxPoint; 
 
}) 
 

 
map.addLayer(auxLayer); 
 

 
map.on('pointermove', function(e){ 
 
    if(e.dragging) return; 
 
    var coord = e.coordinate; 
 
    var distance = 0; 
 

 
    var pointsGeometry = []; 
 

 
    var sourcePointFeature = new ol.Feature({ 
 
    geometry : new ol.geom.Point(coord) 
 
    }); 
 

 
    var closestPoint = lineString.getGeometry().getClosestPoint(coord);     
 
    var lineDiffFeature = new ol.Feature({ 
 
    geometry : new ol.geom.LineString([ 
 
     coord, closestPoint 
 
    ]) 
 
    }); 
 
    for(let i = 0; i< points.length - 1; i++){ 
 
    var p = points[i] 
 
    var next = points[i + 1]; 
 
    var subLineStringGeom = new ol.geom.LineString([ p, next ]); 
 

 
    pointsGeometry.push(p); 
 

 
    var e = 1e-10; 
 
    var extent = [ closestPoint[0] - e, closestPoint[1] - e 
 
        , closestPoint[0] + e, closestPoint[1] + e 
 
       ] 
 

 
    if(subLineStringGeom.intersectsExtent(extent)){ 
 
     //console.log(i); 
 
     pointsGeometry.push(closestPoint); 
 
     distance += wgs84Sphere.haversineDistance(p, closestPoint); 
 
     break; 
 
    } 
 
    distance += wgs84Sphere.haversineDistance(p, next); 
 
    } 
 
    console.log(closestPoint) 
 
    var cpGeometry = new ol.geom.Point(closestPoint); 
 
    var cpFeature = new ol.Feature({ geometry : cpGeometry }); 
 

 
    var geometry = new ol.geom.LineString(pointsGeometry); 
 
    var newFeature = new ol.Feature({ geometry }); 
 

 
    auxLayer.getSource().clear(); 
 
    auxLayer.getSource().refresh(); 
 

 
    auxLayer.getSource().addFeature(lineDiffFeature); 
 
    auxLayer.getSource().addFeature(newFeature); 
 
    auxLayer.getSource().addFeature(sourcePointFeature); 
 
    auxLayer.getSource().addFeature(cpFeature); 
 
    sourcePointFeature.setStyle(styleAuxSourcePoint); 
 
    lineDiffFeature.setStyle(styleAuxLine); 
 
    //console.log(geometry.getLength()) 
 
    console.log(distance); 
 

 
})

html, body, #map { 
 
    width : 100%; 
 
    height : 100%; 
 
    padding : 0px; 
 
    margin : 0px; 
 
}

<script src="https://openlayers.org/en/v3.20.1/build/ol.js"></script> 
 
<link href="https://openlayers.org/en/v3.20.1/css/ol.css" rel="stylesheet"/> 
 
<div id="map" class="map" tabindex="0"></div>