Opened 6 years ago

Last modified 3 years ago

#1066 new defect/bug

Reduce route graph when building

Reported by: mvglasow (2) Owned by: KaZeR
Priority: major Milestone: version 0.6.0
Component: core Version: git master
Severity: normal Keywords: speed, performance, routing
Cc: michael@…

Description

When enabling the route graph, I often see nodes in the graphs which have merely two neighbors, although these are not necessary for routing.

Take the following example of a simplified road graph:

A
|
B---C---D---E
 \         /
  F-------G
 /         \
H           I

We can easily simplify B-C-D-E to B-E, as in points C and D no routing decisions need to be made - when we go from B to C, it is clear that we will proceed in direction D and vice versa. (The cost for B-E would be the sum of B-C, C-D and D-E.)

Currently Navit seems to do that only partly: Curved mountain roads correctly get reduced to a straight line, but every now and then there is a node in the middle of the road. I have observed two conditions for this:

  • Change in road attributes: e.g. tunnel entrances. This may be related to the fact that each change in attributes means that the OSM way ID changes.
  • Nodes which are located at a point where one way joins or crosses another, but not all ways are usable for routing (e.g. footway crossing road when in car mode).

Eliminating such nodes will reduce the memory required for the route graph - memory is currently a limiting factor with long routes, especially with the route_depth attribute introduced in r5216. It will introduce extra processing time to find and eliminate such nodes, but that will be saved again because fewer nodes need to be visited when flooding, I expect no performance changes.

Attachments (1)

06.png (29.4 KB) - added by mvglasow (2) 5 years ago.
Turn in a road with route and route graph

Download all attachments as: .zip

Change History (8)

comment:1 Changed 5 years ago by usul

  • Keywords speed performance routing added
  • Milestone set to version 0.6.0

This seems to depend on what your routing graph is used for. For routing you are right, but if you want to draw the route on the map, shouldn't you draw every node to find your way through the road network?

Not sure if we can realize that idea, but will schedule it for next major release

comment:2 Changed 5 years ago by mvglasow (2)

If I understand that correctly, Navit already omits from the route graph all inner nodes of a way that are not shared with any other way. So if you have a long turn in the road, mapped as a single way, the individual nodes of that turn are not in the route graph, as the route graph is already being reduced to the nodes mentioned before. However, the route display seems to use map data, including the nodes omitted from the route graph. (See attached screenshot of a route following a turn in the road. The road and rute are drawn curved, but the nodes are not in the route graph.)

So the logic to get a geographically correct route from a list of nodes in the route graph seems to be there already. The only change is that we can no longer assume any two neighboring nodes in the route graph to be part of the same way. There may be any number of ways, and the sequence would need to be determined at run-time. That would include some more processing to draw the route but save memory for a lot of nodes. Since the route graph covers all roads within a map rectangle, and the route typically uses a small fraction of them, and typically we are just displaying a fraction of the road, the memory efficiency probably outweighs the extra processing required.

Changed 5 years ago by mvglasow (2)

Turn in a road with route and route graph

comment:3 Changed 4 years ago by mvglasow (2)

  • Severity set to normal

Following up on previous comments: after doing some work on the navigation code, I learned that Navit uses multiple maps. There's the persistent map, i.e. the binfile (or other) map that is used to draw the map on the screen. Then there's the route graph map, which is generated from the persistent map when a route is calculated and has only the nodes needed for the route graph. Reducing the route graoh would only change the latter and have no effect on display.

jandegr just pointed out another example to me. It involves a ramp that shares nodes with a landuse polygon. Each of the shared notes becomes part of the route graph – which is also not necessary because the other way (the landuse polygon) is not routable.

If we want to do this kind of reduction, we need to look at two things:

  • Start/end nodes of ways: since the route involves multiple way objects, we need to find out if Navit will still be able to reconstruct the route if the list of navigation_cmd no longer holds the full list (or what else we need to change for that).
  • Inner nodes shared with non-routable ways: these are probably safe to drop with no further code changes. The challenge here is to tell which ways are "routable" – this may vary depending on the vehicleprofile, so this kind of processing would need to take place when building the route graph (and would need to be repeated when the vehicleprofile changes).

These changes may speed things up or slow them down, or have no measurable impact, and the effect may even vary from route to route. The benefit I see is that it improves memory efficiency, though that is becomming less of a issue as devices are getting more powerful.

comment:4 Changed 4 years ago by tryagain

A small addition regarding case where two osm ways share some or all their nodes: both ways will be split by maptool on each common node. So binmap already has the ramp split, and routing/navigation code would have to merge them, if needed.

I was also considering moving profile processing to the map reading stage. That would improve mem usage and performance at least for some profiles. I do not see a problem in graph rebuild on vehicle profile change, as i do not see usage scenario requiring to change it regularly. But I'm afraid we will lose non routable ways from navigation code, so it will see not all existing turn possibilities, which may affect directions.

comment:5 Changed 4 years ago by mvglasow (2)

Thanks for the clarification – so basically the two cases I mentioned are equivalent in Navit, and in either case we need to make sure we can reconstruct the whole chain of navigation items.

As for "routable" – I should work that out in more detail: For the definition of "routable" I would take only the object type into consideration but not access flags.

This would eliminate nodes shared between a road and anything that is not a road-like object – such as the outlines of landuse/landcover polygons, railroad tracks, administrative borders and similar.

For a car profile, we might also eliminate nodes shared between a road and a cycle path, or a piste – I don't think any driver would consider entering them.

I do realize, however, that we need to pay special attention to ways where the case is less obvious. Assume a bike profile and a set of paths in a park: some are allowed for bikes, others are for pedestrians only. This is often not obvious, so we should retain that information.

A first shot could be to start with objects that no one's ever going to drive/walk on, such as landuse polygons, building outlines, fences and you-name-it, and also eliminate nodes that are shared between exactly two ways and are end nodes of both ways. Once we have the code for that running, we can tackle the less obvious cases.

comment:6 follow-up: Changed 3 years ago by mvglasow (2)

From yesterday's IRC logs (on a different issue but may be of interest here):

16:41 #navit: < tryagain> mvglasow iirc all routable items are defined in item.c inside struct default_flags default_flags2[] array. 16:42 #navit: < tryagain> i think i've hit once a problem with unability to route over a road not in that array

16:47 #navit: < mvglasow> but I have encountered a road some time ago that shared nodes with a landuse polygon and the road was completely segmented, despite being a single way in OSM 16:49 #navit: < tryagain> yeah, it's the way the split works: it does not distinguish item types. But i think it shouldnt be a very common case...

That means we could tweak segmentation code a bit and chop ways in two only where they intersect another way that is routable for some mode of transportation, determined either by checking default_flags2[] (in item.c) or by outright evaluating the access flags of the way (it is routable if flags & AF_ALL is nonzero).

If I put tryagain's earlier comment to this ticket and my understanding of route_process_street_graph() together, segmentation already happens in maptool but the link between segments of the same OSM way remains is preserved: Unlike OSM, Navit distinguishes between coordinates and nodes. Coordinates correspond to OSM nodes that belong to a single way only. Nodes in Navit are OSM nodes linking multiple ways. Map items can have coordinates and nodes in any order. Nodes mark the places at which the item is broken up into segments.

This would mean we could add some logic to route_process_street_graph(): whenever a node is encountered, we would analyze the other items sharing this node and start a new segment only if one of the other ones is routable.

As for reconstructing the route – I learned that the route graph map essentially holds a copy of all ways considered for that route with all nodes and attributes, plus routing costs. The route itself is drawn using the route path, which is a reduction of the route graph containing only ways and nodes which are part of the route. Which means there is no need to refer back to the original map object – we can do pretty much any post-processing we like as we build the route graph, as long as we keep all coordinates with their order and all attributes used for routing and navigation.

comment:7 in reply to: ↑ 6 Changed 3 years ago by tryagain

Replying to http://wiki.navit-project.org/index.php/user:mvglasow (2):

That means we could tweak segmentation code a bit and chop ways in two only where they intersect another way that is routable for some mode of transportation, determined either by checking default_flags2[] (in item.c) or by outright evaluating the access flags of the way (it is routable if flags & AF_ALL is nonzero).

probably yes, but i was thinking to add country information to road mesh, so we can introduce per country rules for routing etc. Though we could reintroduce split at country boundary when needed.

If I put tryagain's earlier comment to this ticket and my understanding of route_process_street_graph() together, segmentation already happens in maptool but the link between segments of the same OSM way remains is preserved: Unlike OSM, Navit distinguishes between coordinates and nodes. Coordinates correspond to OSM nodes that belong to a single way only. Nodes in Navit are OSM nodes linking multiple ways. Map items can have coordinates and nodes in any order. Nodes mark the places at which the item is broken up into segments.

At binfile level, the only nodes present are the ones which contain some POI-like information: POIs themselves, town labels, address infos. Other nodes, including road crossings not tagged with something special like traffic light, are skipped.

At route map level, nodes are reintroduced on every way end, and roads are connected together based on their endpoint coordinates (no osm node id data is present, so we can not recognize two separate crossings at the same coordinates but at different height).

This would mean we could add some logic to route_process_street_graph(): whenever a node is encountered, we would analyze the other items sharing this node and start a new segment only if one of the other ones is routable.

Sounds interesting, but the only implementaion I see would be build the whole route graph in the memory and then pass all its nodes to drop some of them. But that means we still need at some moment amount of memory equal to size of the whole graph.

As for reconstructing the route – I learned that the route graph map essentially holds a copy of all ways considered for that route with all nodes and attributes, plus routing costs. The route itself is drawn using the route path, which is a reduction of the route graph containing only ways and nodes which are part of the route. Which means there is no need to refer back to the original map object – we can do pretty much any post-processing we like as we build the route graph, as long as we keep all coordinates with their order and all attributes used for routing and navigation.

Route graph map does not hold the copy. It holds some essential precomputed data like way type, way length, endpoint coordinates (iirc, in the form of node references), and original item reference. No interior way coordinates are held. Original item reference is memory pointer to the map object and item id. To see what route graph looks like, enable "route graph" map in the settings->maps. You'll see, route graph "ways" (rg_segment) have only two points, but they have street_item attribute which is a reference to their mother item. Click rg_segment (pink arrow) on the map and go to actions -> map point ("globe with coordinates") -> click "rg_segment" in the list of items.

So we can get original item data based on rg_item, but this is actually done by querying underlying map. This query could be extremely fast, if needed tile is already cached in Navit's internal cache. But if that tile is missing from the Navit cache and from the OS cache, such a query would mean reading binfile member from the disk and unzipping it.

Note: See TracTickets for help on using tickets.