graphhopper / graphhopper/graphhopper

Implement heading and pass_through for CH

Open
#2,364 2 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.