graphhopper
graphhopper copied to clipboard
graphhopper
Inaccurate Isochrones/SPT's when intersections are sparse
Describe the bug
One use-case of GH is to create isochrones to show how far one can get, in this case, how far one can get walking from a bus stop. However, these isochrones and SPT's can be fairly imprecise for situations where the time or distance limit is short and the road network is sparse (ie. few intersections like in rural or suburban areas).
To Reproduce
- Create an isochrone or SPT on a road where there are no intersections within the time/distance limit.
Figure 1 - distance_limit=1100m, profile=foot
Figure 2 - distance_limit=1150m, profile=foot
- Alternatively, create an isochrone or SPT on a road where there are few intersections within the time/distance limit (Figures 3 and 4).
Figure 3 - distance_limit=400, profile=foot
Figure 4 - distance_limit=400, origin moved very slightly to the west; profile=foot.
Note that the isochrones above are shown exactly as returned by GH, and aren't processed by any other tools.
Expected behavior Tracing through from the origin to the end of each line in the SPT gives you the distance_limit, which would be similar to what you'd get when making a Service Area in ArcMap.
System Information
GH 3.2
Approach to Resolve
Having looked through the codebase I'm looking for some guidance into what would be required to resolve this issue.
One possible approach I was thinking of is, after having generated the edges in the SPT, extend them along the road away from the origin until the exact distance/time limit is reached. If this ends up degrading performance then making it optional could work for turning it into a PR.
Thanks!
One possible approach I was thinking of is, after having generated the edges in the SPT, extend them along the road away from the origin until the exact distance/time limit is reached. If this ends up degrading performance then making it optional could work for turning it into a PR.
Yes, absolutely. I think this is on the right track, and I don't think this will impact performance much. I would totally merge this, without a feature switch.
The only broad question I can think of is -- can this be done (correctly, in all cases) by post-processing the SPT as it is now, or do we need to drill into the Dijkstra search that builds the SPT, i.e. should we (must we) specialize the Dijkstra search and teach it what road segments are, and that you don't need to traverse them fully.
(Consider this question for "node based" and "edge based" search.)
We would be very interested in this implementation as well, our blog post (sorry it's a bit lengthy) contains some issues with the current isochrone implementation and incomplete OSM data: https://www.gispo.fi/en/blog/analyzing-school-accessibility-on-qgis/
Tl;dr: Our idea would be to just buffer the accessible network with a constant buffer to create the polygons. Is this too simple, do you believe travel time across terrain should be taken into account too? That would cause problems when roads are sparse. I believe we cannot assume that all terrain is traversable starting from the road network, since in reality there will be obstacles, some of them insurmountable.
In networks with low connectivity (think US suburbs with missing pedestrian connections), some locations might be very close to each other physically, but they can only be accessed by foot by taking a very long detour, and we cannot assume such locations can be reached across terrain. Similarly with any buildings, fences, railroads, rivers etc. or practically any man-made or natural obstacles.
It would make more sense for us to use a smallish buffer (buffer width defined by the user) instead of assuming that all points are accessible from the road.
@Rikuoja Thanks! Before reading your blog post, let me just quickly say that, in my mind, that's a slightly different issue: How is an (abstract) isochrone on a road network extended to an isochrone in the terrain.
This here is more specifically (and more simply) about making the isochrone on the road network more fine-grained. At the moment, it basically snaps to intersections, leading to inaccuracies when intersections are sparse (rather than roads), and that would even be rather easy to fix.
The issue you're raising is much broader.
@michaz A good point! Indeed, just adding nodes or intersections where they are sparse would go a long way to making the isochrone shape closer to reality, sounds like a good start.
Hey @michaz , took a stab at this over at #2838 based on your approach described above.
