Improving elevation profiles for short routes

I self-host graphhopper for a use-case that typically involves shorter routes where users (runners, walkers, and bikers) want to see all of the bumps along the way and know how much they’ve climbed/descended. Currently, I sample the 2D route and find the elevation at each point along the route to get elevation profiles. I’m interested in adding elevation into graphhopper data to save on latency, bandwidth, leverage bridge/tunnel interpolation, and get more accurate total ascent/descent over long routes. I’ve noticed a few issues though that make the graphhopper elevation profiles not quite usable for this purpose:

To fix these I was thinking of submitting these PRs that I’ve prototyped and appear to solve the problems but I want to get some feedback on the overall plan first:

  1. Implement bilinear interpolation in HeightTile.java to approximate elevations better between elevation data samples
  2. Post-process all way geometries to insert “sampled” points between any adjacent points that are further apart than a configurable threshold. So if you set the sample distance to 30m and 2 consecutive points are 25m apart it does nothing, but if they are 60m apart, one point would be inserted halfway between them.
  3. Make the Douglas Peucker polyline simplification implementation elevation-aware so that it still throws out points along a long straight road in the desert, but it keeps the important points defining the elevation profile for a long straight road over a mountain.

Let me know if you think these proposed changes make sense, what you think should be enabled by default vs. opt-in config, or if you’d rather move this discussion into a github issue.

Thanks

This is really interesting, thanks! What source for the elevation data are you using?
btw: have a look into the recently contributed PR: https://github.com/graphhopper/graphhopper/pull/1929

Post-process all way geometries to insert “sampled” points between any adjacent points that are further apart than a configurable threshold.

Do you know what this means in terms of storage increase for e.g. Germany (or Europe or world wide)?

Make the Douglas Peucker polyline simplification implementation elevation-aware

What does this mean exactly? Will it remove the point only if elevation delta is less than e.g. 1m? As we apply the douglas peucker on import and on query: is this change only required for the import?

Yes, I opened that PR :slight_smile: sorry, my github handle and username here don’t match up! My site uses mapzen data by downloading the elevation-encoded PNGs and decoding in the browser (more details here). When I prototyped these proposals with mapzen SRTM data in graphhopper, the elevation profiles looked almost exactly the same as the site shows now.

What does this mean exactly? Will it remove the point only if elevation delta is less than e.g. 1m? As we apply the douglas peucker on import and on query: is this change only required for the import?

2d Douglas Peucker removes a point if the line moves less than some threshold (1m) away from that point without it, 3d Douglas Peucker does the same thing, it just is does the distance computation in 3d space (see https://github.com/mourner/simplify-js/blob/3d/simplify.js as an example implementation). We could probably have a configurable weight on the elevation parameter, for example Douglas Peucker could have a 1m threshold in lat/lon but 5m in elevation so you can tune increased size vs. resolution. I think we’d want import and query to both use this when elevation is enabled.

Do you know what this means in terms of storage increase for e.g. Germany (or Europe or world wide)?

I remember the edge geometries were bigger when I prototyped this before, but I don’t recall how much. I imagine that would vary quite a bit based on the values you choose for distance threshold and the 3d simplification factor. Maybe I’ll open up an experimental PR to get these both working and post some stats for different parameters so we can decide how/if to proceed?

Any concerns about bilinear interpolation?

hah :smiley: nice, thanks!

Maybe I’ll open up an experimental PR to get these both working and post some stats for different parameters so we can decide how/if to proceed?

Sounds good!

Any concerns about bilinear interpolation?

No, I just forgot to mention that I would really like to have something like this! Probably we can then remove our ‘calcMean’ approach.

Alright, I opened https://github.com/graphhopper/graphhopper/pull/1942 for bilinear interpolation and re-prototyped the 3D polyline simplification/edge sampling. Looks like based on the threshold you choose for sampling long edges, and weight given to elevation during simplification the worst case edge geometry file size increase is 30%, but there are reasonable combinations that keep the increase under 10-15%. I also found that there is a separate improvement we can make to reduce edge geometry file size by 15% across the board, which helps offset this increase.

The change got fairly large though (see diff here) and includes:

  • Some DistanceCalc refactoring to add 3D distance capabilities to all DistanceCalc implementations and remove DistanceCalc3D
  • Making Douglas Peucker elevation-aware and wiring through the elevation factor param
  • Sample edges during import and wire through the edge sampling distance
  • The improvement to reduce edge geometry file size by 15%

Think I should keep that all together in 1 PR or split up?

This sounds really good. And yes, it would be nice to have smaller PRs, then review can be faster (in theory :wink: ) and certain bigger changes, e.g. that cause the size increase, could be longer tested before merging.

I also found that there is a separate improvement we can make to reduce edge geometry file size by 15% across the board, which helps offset this increase.

This is nice and would be also nice to have this separated as it fixes https://github.com/graphhopper/graphhopper/issues/1353

Powered by Discourse