2

For my question I have prepared a JsFiddle demo which works well and is fun to play around with:

animated map

My question is neither about JavaScript nor OpenStreetMap though.

It is about mathematics.

When you drag the marker around and release it, I send an Overpass API query to retrieve the nearby way objects with non-empty highway tag and then draw them as blue Leaflet polylines with clickable popups attached to them.

Then I iterate through the retrieved way objects and for each way segment (defined by the list of way nodes) I try to determine the distance from the draggable marker to the way segment.

Finally the closest segment is drawn as a red polyline and the shortest distance is visible in its popup and also logged to the browser console -

// calculate the minimal distance between a location at x, y
// and a line connecting a node at x1, y2 with a node at x2, y2
// QUESTION: this algorithm uses cartesian coordinates, 
// but how to use it with latitudes and longitudes?
function distancePointSegment(x, y, x1, y1, x2, y2) {

  var a = x - x1;
  var b = y - y1;
  var c = x2 - x1;
  var d = y2 - y1;

  var dot = a * c + b * d;
  var segmentLengthSquared = c * c + d * d;
  var param = (segmentLengthSquared === 0 ? -1 : dot / segmentLengthSquared);

  var closestSegmentPointX;
  var closestSegmentPointY;

  // the closest point is the end node at x1, y1
  if (param < 0) {
    closestSegmentPointX = x1;
    closestSegmentPointY = y1;
  }
  // the closest point is the end node at x2, y2
  else if (param > 1) {
    closestSegmentPointX = x2;
    closestSegmentPointY = y2;
  }
  // the closest point is located inside the segment
  else {
    closestSegmentPointX = x1 + param * c;
    closestSegmentPointY = y1 + param * d;
  }

  var dX = x - closestSegmentPointX;
  var dY = y - closestSegmentPointY;

  return Math.sqrt(dX * dX + dY * dY);
}

function findNearestWayId(ways, nodes) {
  var markerPosition = draggableMarker.getLatLng();
  var shortestDistance = Number.MAX_VALUE;
  var nearestWayId;
  for (var wayId in ways) {
    var prevNodeLat = Number.NaN;
    var prevNodeLng = Number.NaN;

    var way = ways[wayId];
    // iterate all nodes of a way object and save their positions
    // as a list of Leaflet latLng objects in the way object
    way.latLngs = [];
    // also save the minimal distance from the way object to the marker position
    way.minDistance = Number.MAX_VALUE;

    for (var n in way.nodes) {
      var nodeId = way.nodes[n];
      var node = nodes[nodeId];
      way.latLngs.push(node.latLng);

      // find the minimal distance among the segments of the way
      if (!isNaN(prevNodeLat) && !isNaN(prevNodeLng)) {
        var distance = distancePointSegment(
            markerPosition.lat, 
          markerPosition.lng, 
          prevNodeLat, 
          prevNodeLng, 
          node.latLng.lat, 
          node.latLng.lng
        );
        if (distance < way.minDistance) {
          way.minDistance = distance;
        }
      }

      prevNodeLat = node.latLng.lat;
      prevNodeLng = node.latLng.lng;
    }

    // find the overall shortest distance among all ways
    if (way.minDistance < shortestDistance) {
      shortestDistance = way.minDistance;
      nearestWayId = wayId;
    }
  }

  return nearestWayId;
}

// draw ways as polylines with popups
function drawPolylines(ways, nearestWayId) {
  var markerPosition = draggableMarker.getLatLng();
  for (var wayId in ways) {
    var way = ways[wayId];
    var line = L.polyline(way.latLngs, { color: (wayId === nearestWayId ? 'red' : 'blue') });

    var markerLatStr = parseFloat(markerPosition.lat).toFixed(6);
    var markerLngStr = parseFloat(markerPosition.lng).toFixed(6);

    var popupMsg = '<p>Way: <a href="https://www.openstreetmap.org/way/' + wayId + '" target="_blank">' + wayId + '</a></p>' + 
        '<p>Distance to the car at<br>' + markerLatStr + ',' + markerLngStr + ': ' + way.minDistance + '</p>';
    line.bindPopup(popupMsg);

    line.addTo(lineGroup);
  }
}

function processOverpassReply(data) {
  var ways = { };
  var nodes = { };

  console.log('Received Overpass API reply with ' + data.elements.length + ' elements');
  for (var i = 0; i < data.elements.length; i++) {
    var element = data.elements[i];
    var type = element.type;

    if (type === 'way') {
      var wayId = element.id;
      ways[wayId] = element;
    } 
    else if (type === 'node') {
      var nodeId = element.id;
      var nodeLat = element.lat;
      var nodeLng = element.lon;
      nodes[nodeId] = element;
      element.latLng = L.latLng(nodeLat, nodeLng);
    }
  }

  var nearestWayId = findNearestWayId(ways, nodes);
  console.log('The nearest way id: ' + nearestWayId + ' with the shortest distance: ' + ways[nearestWayId].minDistance + ' will be drawn in red color');
  console.log(ways);
  console.log(nodes);
  drawPolylines(ways, nearestWayId);
}

function sendOverpassRequest() {
  var markerPosition = draggableMarker.getLatLng();
  // return ways and nodes with non-empty "highway" tag around the draggable marker position
  var query = 'way(around:20,' + markerPosition.lat + ',' + markerPosition.lng + ')[highway~"."];(._;>;);out;';
  console.log('Sending Overpass API query: ' + query);

  if (overpassLayer != null) {
    // remove all lines
    lineGroup.clearLayers();

    map.removeLayer(overpassLayer);
    overpassLayer = null;
  }

  overpassLayer = new L.OverPassLayer({
    minZoom: 9,
    maxZoom: 18,
    endPoint: 'https://overpass-api.de/api/',
    query: query,
    onSuccess: processOverpassReply
  });

  map.addLayer(overpassLayer);
}

function sendOverpassRequest() {
  var position = draggableMarker.getLatLng();
  // return ways and nodes with non-empty "highway" tag around the draggable marker position
  var query = 'way(around:' + 50 + ',' + position.lat + ',' + position.lng + ')[highway~"."];(._;>;);out;';
  console.log('Sending Overpass API query: ' + query);

  if (overpassLayer != null) {
    // remove all lines
    lineGroup.clearLayers();

    map.removeLayer(overpassLayer);
    overpassLayer = null;
  }

  overpassLayer = new L.OverPassLayer({
    minZoom: 9,
    maxZoom: 18,
    endPoint: 'https://overpass-api.de/api/',
    query: query,
    onSuccess: processOverpassReply
  });
  map.addLayer(overpassLayer);
}

var startPosition = [51.4661, 7.2491];
var zoomOptions = {
  minZoom: 9,
  maxZoom: 18
};

var map = L.map('map', zoomOptions).setView(startPosition, 16);
L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
  attribution: '&copy; <a href="https://www.openstreetmap.org/copyright">OpenStreetMap</a> contributors'
}).addTo(map);

var draggableMarker = L.marker(startPosition, {
  draggable: true
})
.addTo(map)
.on('dragend', sendOverpassRequest);

var lineGroup = L.layerGroup();
map.addLayer(lineGroup);

var overpassLayer;

sendOverpassRequest();
html,
body {
  padding: 0;
  margin: 0;
  height: 100%;
}

body {
  display: flex;
  flex-direction: column;
}

#map {
  flex-grow: 1;
}
<link type="text/css" rel="stylesheet" href="https://cdn.jsdelivr.net/npm/leaflet@1/dist/leaflet.css">
<link type="text/css" rel="stylesheet" href="https://cdn.jsdelivr.net/npm/leaflet-overpass-layer@2/src/OverPassLayer.css">
<script src="https://cdn.jsdelivr.net/npm/leaflet@1/dist/leaflet-src.js"></script>
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/OverPassLayer.bundle.js"></script>

<div id="map"></div>

The heart of my demo is the distancePointSegment(x, y, x1, y1, x2, y2) function, which calculates the minimal distance between a point (x, y) and a line segment defined by the end nodes (x1, y1) and (x2, y2).

I have found it at https://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment/6853926#6853926 and I understand well, how it works.

There are 2 edge cases and then the main case, when the height falls on the line segment...

However the function (and there are lots of similar implementations on the net) is meant for cartesian coordinates space and expects coordinates as parameters.

While I pass the latitudes and longitudes... which is wrong.

And when you play around a bit longer with my test case, you will see that sometimes not the closest way segment is painted red, as a consequence of my error.

How can I find a good method to calculate the short distance between a location and a line segment on the spherical map.

1 Answer 1

4

In such cases the best strategy is to use existing solution/library, and in this case that would be turf.js library and it's method turf.nearestPointOnLine (see https://turfjs.org/docs/#nearestPointOnLine) which does exactly would you need:

Takes a Point and a LineString and calculates the closest Point on the (Multi)LineString.

So in your case distancePointSegment function could look something like this (code taken from official turf.js example):

function distancePointSegment(lat, lng, lat1, lng1, lat2, lng2) {
  var pt = turf.point([lng, lat]);
  var line = turf.lineString([
    [lng1, lat1],
    [lng2, lat2]
  ]);
  var snapped = turf.nearestPointOnLine(line, pt);
  
  return(snapped.properties.dist);
}
4
  • Thank you, it looks like a great library with a generous license! Apr 7, 2023 at 15:44
  • Hi TomazicM your suggested code works perfectly, but when I try to optimize it by passing all way nodes at once to the turf.lineString as in the distancePointSegmentBroken then the result is very different... do you know why? Apr 9, 2023 at 14:54
  • 1
    I would say this is a separate question, otherwise it can go ad infinitum in comments.
    – TomazicM
    Apr 9, 2023 at 17:37
  • That makes sense! I have asked my new question here: gis.stackexchange.com/q/457269/222231 Apr 9, 2023 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.