graphhopper / graphhopper/graphhopper
Implement heading and pass_through for CH
- Dominant language
- Java
- Stars
- 6.7k
- Forks
- 2k
- Avg merge
- 15h 58m
- Merged PRs (30d)
- 3
Description
For edge-based CH this is not a problem, but even for node-based CH it is possible, at least in theory. I'm just not sure if it is worth the effort.
The problem with node-based CH is described here: https://github.com/graphhopper/graphhopper/commit/e8cdc6fb0afa8810fb4074aafee13fc2c0eb46e3
I think an easy way to do it with node-based CH would be this:
1) find adjacent nodes next to start node (A, B, C)
2) calculate all routes A,B,C -> target node with an initial weight for A,B,C (zero for the heading direction and including a penalty otherwise)
3) reject all routes that visit the start node (A->start->target) for example
4) pick the shortest remaining route
5) prepend the start node to this shortest route
Slightly more complicated, but more efficient would be:
1) see above
2) do a multi source query (A,B,C)->target with initial weights, but also use an edge filter that filters out edges going to the start node for the first expansion. this requires unpacking shortcuts for the first expansion!
3) prepend the start node to the resulting route
pass_through should work the same way.
Contributor guide
Assessment
This issue has not been assessed yet.