Leaflet Polylines: Find the minimum distance to another LatLng

So, the user is at a location (a L.LatLng instance, perhaps the map center or perhaps the latlng from a locationfound event). And out on the map there are trails, in the form of L.MultiPolyline instances. Question: What trails have any presence within a 5-mile circle of my location, and for bonus points how far away is the closest part of that trail?

In our case, we're writing the application 100% client-side, so I can't cop out and bounce it off PostGIS. And we don't need to go all the way with JSTS so we can buffer and find intersection. What we really need is to find the closest approach of the line to this point, and see whether that is within the given circle.

There are two ways to do this: one is correct and slow, the other is quick and dirty. The correct way involves complicated math and would be comparatively slow, and when we're going over several hundred MultiPolyline instances the speed boost is worth the sloppiness. The fast way is to find the closest vertex of the MultiPolyline, and its distance to our LatLng. This is a lot simpler and faster than the mathematical way, and in our case the sloppiness is not relevant: we're looking at a scale of miles and our vertices aren't so far apart that it'll matter.

For more info and downloads:
https://github.com/gregallensworth/Leaflet/blob/master/MultiPolyLine_Distance.js

Quick and Dirty

The brute force way: Loop over all vertices in the given Polyline or MultiPolyline, and track the one with the minimum distance as determined by LatLng.distanceTo() Super simple:

// search this Polyline for the closest vertex to the given LatLng
// return an object of both that vertex (LatLng instance) and the distance (meters)
L.MultiPolyline.prototype.calculateClosestVertexAndDistance = function (targetlatlng) {
    var closest_latlng = null;
    var closest_meters = 1000000000;

    var paths = this.getLatLngs();
    for (var pi=0, pl=paths.length; pi<pl; pi++) {
        var path = paths[pi];

        for (var vi=0, vl=path.length; vi<vl; vi++) {
            var d = path[vi].distanceTo(targetlatlng);
            if (d >= closest_meters) continue;
            closest_latlng = path[vi];
            closest_meters = d;
        }
    }

    return { latlng:closest_latlng, meters:closest_meters };
}
L.Polyline.prototype.calculateClosestVertexAndDistance = function (targetlatlng) {
    var closest_latlng = null;
    var closest_meters = 1000000000;

    var verts = this.getLatLngs();
    for (var vi=0, vl=verts.length; vi<vl; vi++) {
        var d = verts[vi].distanceTo(targetlatlng);
        if (d >= closest_meters) continue;
        closest_latlng = path[vi];
        closest_meters = d;
    }

    return { latlng:closest_latlng, meters:closest_meters };
}

Usage is about as simple as it looks:

var trail = L.polyline([vertices...]);
var here = map.getCenter();

var closest = trail.calculateClosestVertexAndDistance(here);
var title = "This spot is " + (closest.meters / 1609.34).toFixed(2) + " miles away";
L.marker(closest.latlng, { title:title}).addTo(MAP);

Quicker, but not Dirtier

Here's an idea. That "vertex finder" gives the closest vertex. But what if the entire trail or the majority of it were within a given circle? If your specific use case is simply to know whether the trail has any vertex within your search radius, you could stop at the first vertex whose distanceTo() is under the given radius.

That's what this does:

L.MultiPolyline.prototype.hasVertexWithinRadius = function (targetlatlng,meters) {
    var paths = this.getLatLngs();
    for (var pi=0, pl=paths.length; pi<pl; pi++) {
        var path = paths[pi];

        for (var vi=0, vl=path.length; vi<vl; vi++) {
            var d = path[vi].distanceTo(targetlatlng);
            if (d <= meters) return true;
        }
    }

    // if we got here, we never did find a vertex within range
    return false;
}
L.Polyline.prototype.hasVertexWithinRadius = function (targetlatlng,meters) {
    var verts = this.getLatLngs();
    for (var vi=0, vl=verts.length; vi<vl; vi++) {
        var d = verts[vi].distanceTo(targetlatlng);
        if (d <= meters) return true;
    }

    // if we got here, we never did find a vertex within range
    return false;
}

Since this one won't test every single vertex even after it has found an answer, it should run slightly faster if "is in range" is your only need. If you have several hundred lines, especially if you allow for a search radius which may match most vertices within any matching trails, this could shave off the milliseconds.

Usage:

var trail = L.polyline([vertices...]);
var here = map.getCenter();

var within = trail.hasVertexWithinRadius(here);
alert( within ? 'Close' : 'Too far' );

Enjoy!

Wait, it doesn't work (under a microscope)!

This isn't a true "minimum distance between point and line" algorithm, and there is a case where it will fall down. If the vertices are far apart compared to the radius of your circle, you may get a false negative: the vertices may be further away than the line between them. This illustration should... illustrate.

In this case, the line would not be matched since no vertices are within the given radius. But again, this is fairly contrived: your vertices must be very far apart (long straight segments) relative to the radius. But for a realistic use case of trails (vertices a few dozen meters apart) and large circles (5 miles) it does work well.

When it comes to finding actual minimum distance, that takes some significant algebra. See my next posting, where this is exactly what I do (though not in Leaflet).