Project-OSRM
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.
seems the linked screenshots don't show tho in the PR
I re-uploaded them. Do they show now?
seems the linked screenshots don't show tho in the PR
I re-uploaded them. Do they show now?
They do. Thanks a lot
Had a first look at the change. First of all, great feature! I think this has been on the todo list for more than 10 years 😀
The main question I have is that we should probably own the Dijkstra implementation that is used and not fall back to boost.
Do we have a general dislike for boost? Just asking ...
Perhaps 😉
Also, routing is our expertise and we should own all routing logic.
Dijkstra in itself is trivial to implement. The hardest piece is the priority queue, if we don't want to take the one in boost. They use a 4-ary heap. A binary heap will do for our problem sizes. I will look into this.
The good news is that heap implementations already exist in our code base:
- include/util/binary_heap.hpp
- include/util/d_ary_heap.hpp
just tweaked the settings s.t. GitHub Actions should now run automatically on push.
I have now implemented Dijkstra and a binary heap that works with it. The d-ary heap in include/util/d_ary_heap.hpp looks like it could be coaxed into service too, but it is completely undocumented.
Shouldn't we drop / update the macos-x64 build since it is based on apple-clang-14? All other builds use clang >= 16.
It's great that “area routing” is getting some attention again. The algorithms and implementations are available (see, for example, this comment and the follow-up posts seven years(!) ago)...
I was recently made aware of this missing feature when I was testing my “vampire mode” - an OSRM profile for pedestrians that prefers shady streets...
Taking full advantage of this may require new tags for areas where it's not clear whether they are traversable or not (for example a natural=forest). This discussion is relevant: https://community.openstreetmap.org/t/tagging-a-traversable-area/138357
