Wie berechnet man einen Abstand zwischen zwei Punkten entlang eines Pfades?

Question

Ich benutze Openlayers3 und ich habe die codierte Geometrie. Ich kann die Koordinaten (lat, lng) für alle Punkte im Pfad bekommen (ungefähr 500 Punkte pro Pfad). Wie berechne ich den Abstand zwischen dem Anfang des Pfades bis zu diesem Punkt, wenn ein zufälliger Punkt innerhalb des Pfades gegeben ist?

Ich habe einen Blick auf Turfjs geworfen und es sieht sehr vielversprechend aus, aber die Lösung, die ich mir vorgestellt habe, wäre nicht sehr nett. Unter Verwendung eines zufälligen Punktes (p1) könnte ich den Punkt (p2) des Weges entdecken, der p1 am nächsten ist, dann ein neues Polygon erzeugen und seine Gesamtdistanz berechnen. Es kann Leistungsprobleme geben, obwohl die Suche O (log n) und das neue Polygon O (n) wäre.

EDIT: der zufällige Punkt ist nicht unbedingt im Pfad, es ist eine GPS-Koordinate und es gibt einen Spielraum für Fehler.

EDIT 2: Schätzung über die Anzahl der Punkte war weg, hat jeder Weg über 500 Punkte, nicht 5k

jemand einen besseren Ansatz kennt? Ich bin nicht sehr erfahren mit Openlayers3 oder Turfjs.

Answer 1

Wie Sie erwähnten Sie verwenden Openlayers 3, ich habe ein Beispiel getan OpenLayers 3 verwenden, ist die Idee:

1. Closest Point across the LineString

2. Iterate über Linestring Punkte eine Koordinate gegeben Holen Sie sich das Berechnen Abstand der einzelnen Pfade und sehen, ob unser nächster Punkt den individuellen Pfad schneidet.

/* 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>