osrm-backend
osrm-backend copied to clipboard
Area Routing
This PR provides routing over areas.
It builds a visibility graph of the area, then runs dijkstra from each entry point to reduce the number of edges, then adds the remaining edges as ways to the router.
From the OSM site, without area routing, following mapped-for-the-router ways:
With area routing, also note the better directions:
Documentation
Issue
Fixes #64 #2655 #7146
Tasklist
- [X] CHANGELOG.md entry (How to write a changelog entry)
- [ ] update relevant Wiki pages
- [X] add tests (see testing documentation)
- [ ] review
- [ ] adjust for comments
TODO
- entrances to buildings along the perimeter of the area,
- PT stations in the middle of the area,
- alternate algorithms, eg. retraction.