Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Always return a route #86

Open
HarelM opened this issue Mar 22, 2023 · 3 comments
Open

Always return a route #86

HarelM opened this issue Mar 22, 2023 · 3 comments

Comments

@HarelM
Copy link

HarelM commented Mar 22, 2023

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
Copy link
Author

HarelM commented Mar 23, 2023

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.

@pbvahlst
Copy link

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
Copy link
Author

HarelM commented Mar 24, 2023

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;
    }```

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants