Hacker News
More precise elevation data for GraphHopper routing engine
usrusr
|next
[-]
DEM just aren't good for routing in a road network. What you want is a data model that stores elevation along the paths in the graph, not a 2D height field. Some routing tools specific to cycling do this, using numbers from barometric recording during actual rides, but even there it's rare and when you know what to look for it's easy to recognize the ones that try to get by with just a DEM.
An acceptable compromise could be precomputed elevations-along-the-path from DEM, that factor in semantic map information like tunnels and non-grade crossings, and turn up filtering to eleven when the DEM grid has a strong grade in a direction that isn't roughly the direction of the path.
lifis
|next
|previous
[-]
One can start assuming that the world is square tiled with square corners on the elevation measurement grid, and assuming that elevation in the square lies between the minimum and maximum value.
Now a road can be split into curve segments such that each segment lies in exactly one square. Then the profile of the road can be determined by guessing the altitude for the midpoint of each curve segment and interpolating.
The altitudes should be guessed to approximately minimize the road length and I think good and fast algorithms are easy to find.
For example, the altitudes of the midpoints can be assigned with a greedy/lazy approach: once one is determined, for each neighbor pick the closest valid altitude until all are assigned. To start, pick the maximum n such that the first n segments have non-empty altitude interval intersection and pick for all of them the endpoint of the intersection interval that is closest to the next interval (or the middle of the intersection interval if there is no next one).
Alternatively it can be formulated as a constraint problem with linear constraints and an objective function that depends on the interpolation. If weighted sum of absolute values is chosen, it's a linear program, otherwise the objective function will have higher degree
bloudermilk
|next
|previous
[-]
jeffbee
|root
|parent
[-]
Example: this DEM thinks there is a local discontinuity where a cyclist will ascend at +22% where this street crosses a buried freeway. https://graphhopper.com/maps/?point=37.80737%2C-122.279329&p...
yorwba
|root
|parent
[-]
oflebbe
|next
|previous
[-]
sarnu
|root
|parent
[-]
jeffbee
|root
|parent
[-]
qwhelan
|root
|parent
|next
[-]
jeffbee
|root
|parent
[-]
1: And their planner, in general, is garbage. I usually take the output file and run it through an AI system to fix it so it doesn't try to cue me to pointlessly switch to the other side of a major road and ride on the sidewalk.