How to calculate a distance between two points along a path?

Question

I'm using openlayers3 and I have the encoded geometry. I can get the coordinates (lat,lng) for all points in the path (around 500 points per path). Given a random point inside the path, how do I calculate the distance between the beginning of the path up to that point?

I've taken a look at turfjs and it looks very promising, but the solution I pictured using it wouldn't be very nice. Taking a random point (p1), I could discover the point (p2) of the path that is closest to p1, then generate a new polygon and calculate its total distance. It may have performance issues, although the search would be O(log n) and the new polygon O(n).

EDIT: the random point is not necessarily inside the path, it's a GPS coordinate and there's a margin for error.

EDIT 2: estimation on the number of points was off, each path has about 500 points, not 5k

Does anyone know of a better approach? I'm not very experienced with either openlayers3 nor turfjs.

Answer 1

As you mentioned you're using OpenLayers 3, I've done an example using OpenLayers 3, the idea is:

1. Get Closest Point across the LineString given a coordinate

2. Iterate over LineString points calculating the distance of each individual paths and see if our closest point intersects the individual path.

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