Point - multiline search?

[diwic]

Hi!

I’m investigating whether Graphhopper could be used for my use case, which is to find the shortest/best path from a point to a trail; where a trail is (by geoJson terminology) a MultiLineString. This particular Multilinestring is composed of approx 200 lines and 100.000 points in total.

So I would go something like 1) start a Graphhopper instance 2) load OSM data 3) load the multiline 4) do tons of searches from different points to find the closest way from that point to anywhere on the multiline.

Is this a feature that Graphhopper supports (if so, some pointers would be highly appreciated), or is Graphhopper point-to-point only?

[Sam_Crawford]

I do something very similar in one of my projects, but I don’t use GH for this aspect of it. I do use GH for the routing, of course.

To achieve what you’re describing, I load all of the multilinestrings into Postgres/PostGIS, and then query these from my Java app before starting the routing process. PostGIS has very good indexing of geometry data, so this works efficiently for planet-wide data for me. Specifically I use the ST_ClosestPoint function (ST_ClosestPoint) to find the nearest point on the trail to the user’s start location.

Hope this helps!

[diwic]

Hi and thanks for your reply;

So your idea is to first find the closest point on the trail using PostGIS/ST_Closestpoint (or some other geometrical library) and then do a point-to-point search using GH?

Not sure if that would work well enough for me. The point on the trail that is geometrically closest could be quite far away from the closest point on the trail w r t the road network. Right?

[Sam_Crawford]

You’re correct. And yes, this can lead to some problematic scenarios, especially around rivers.

I’m not sure if what you’re describing is possible with GH, I don’t think it is out of the box. Basically you want to find the fastest path from Point A to any point on LineString B. I suspect this could be achieved, but it’d require quite some fairly deep changes.

[karussell]

@diwic

PostGIS/ST_Closestpoint

If I understand it correctly what this function does then you should be able to do this calculation directly in JavaScript: graphhopper-maps/src/turnNavigation/GeoMethods.ts at fda5dd835194b1ca0a8fe774384e459537d153b3 · graphhopper/graphhopper-maps · GitHub (and this is also only copied from our Java code)

To really pick the best path you need to map match the trail and get back the edges or nodes and then use DijkstraOneToMany or a normal Dijkstra (DijkstraBidirectionRef) with many destinations initialized (multiple calls to initTo). A bit more complicated but should be doable with the Java library

[diwic]

Just to follow up; I ended up with a different solution that seems to work reasonably well. For every point, I

1. run a “shortest path tree” calculation with a reasonable max distance
2. sort the result by distance ascending
3. search the list until I find a point close enough to my multiline
4. backtrack using prev_node_id to get the route from the point to the multiline

I couldn’t find any documentation for the /spt web server endpoint, but by reading SPTResource.java I could figure out what parameters I could send to the endpoint.