perliedman/geojson-path-finder

Always return a route

Opened this issue · 3 comments

HarelM commented

When the start or end point are not close enough to the graph there is no path results, or at least this is what I've seen in the demo page, I have yet to take this library for a spin.
It would be great if there was an option to return a route from the closest point on the graph to the start and end, this way, if you have a valid graph you will always have a path results.
Am I missing something in the docs?
Generally speaking, this is how graphhopper works and I think it's a good feature to always try and return a route.

HarelM commented

This is documented basically:

Where start and finish are two GeoJSON point features. Note that both points have to be vertices in the routing network; if they are not, no route will be found.

So I would like to reduce this requirement in general.

I don't think that is a job for the library. It would then require more configuration, e.g. how far away is reasonable, if you have a small set of routes in Spain and click Greenland as a starting point and India as the end point, should it then still return a route?

For my project I calculate them myself by having a threshold of 5km "off-road". So when clicking the map I calculate a bounding box with a 5km radius and then use that bounding box to test which road-segment's bounding box intersects. This just to make a quick calculation of possible candidates. If you have many roads you could segment them into larger bounding box groups.
When you have the possible candidates run through the points on the GeoJSON line-string and find the actual point with the smallest distance to the point clicked by e.g. using turf.distance()

HarelM commented

Yes, I just implemented that, but I think that it should be part of this routing library.
I'll add the code at the end if anyone is interested.
Here's another scenario that is currently not supported but I think should be:
You have a starting point which is not on a vertex, and you want the library to find the route.
If you simply select the closest vertex, or the closest vertex on the closest line you might get an incorrect results.
Here's an example of selecting the closest vertex:
image
As can be seen in the image, the start and end points are on the path, but they are not vertices, so the path finder start a bit after the first point and finish a bit after the last point... This is not a great UX. I'm sure I'm not the first to stumble across this.
We are using graphhopper on the server side and I want to introduce this as a back when there's no connection.
Graphhopper does exactly this - finds the closest projected point on the closest line and does the routing using it.
I think this is the expected UX from this library.
I'll be happy to help out contributing to this code base.

Here's the code I wrote to fix both issues, it uses turf obviously and is performed before the graph is created.
This is less than ideal if I would like to cache the graph...

    /**
     * This method will insert a single point to the closest line in the collection.
     * The point that will be added will be on the closest segment of the closest line.
     * @param latlng the point to add a projected version to the closest line
     * @param collection the collection of all the lines to test against
     * @returns the projected point
     */
    public static insertProjectedPointToClosestLine(latlng: LatLngAlt, collection: FeatureCollection<GeoJSON.LineString>) {
        let closetLine = null;
        let nearestPoint = null;
        let minimalDistance = Infinity;
        let coordinates = SpatialService.toCoordinate(latlng);
        for (let feature of collection.features) {
            let point = nearestPointOnLine(feature, coordinates, )
            if (point.properties.dist < minimalDistance) {
                minimalDistance = point.properties.dist;
                closetLine = feature;
                nearestPoint = point;
            }
        }
        closetLine.geometry.coordinates.splice(nearestPoint.properties.index + 1, 0, nearestPoint.geometry.coordinates);
        return nearestPoint.geometry.coordinates;
    }```