Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#1291 closed defect/bug (fixed)

navigation_itm.way->next list has duplicates

Reported by: mvglasow (2) Owned by: KaZeR
Priority: minor Milestone: version 0.6.0
Component: core Version: git master
Severity: normal Keywords:
Cc: http://wiki.navit-project.org/index.php/user:mvglasow, (2)

Description

In maneuver_required2() (and possibly other functions), when cycling through the items of new.way->next, some ways are enumerated more than once.

To test, apply the following patch:

@ -1262,10 +1262,11 @@ maneuver_required2(struct navigation *nav, struct navigation_itm *old, struct na
 				} else if (w->item.type != type_ramp) {
 					num_other++;
 				}
 				if (w != &(new->way)) {
 					dw=angle_delta(old->angle_end, w->angle2);
+					dbg(lvl_debug, "- Examining allowed way: %s %s %s, delta=%i\n", item_to_name(w->item.type), w->name1, w->name2, dw);
 					if (dw < 0) {
 						if (dw > left)
 							left=dw;
 						if (dw > -curve_limit && d < 0 && d > -curve_limit)
 							dc=dw;

Testing a short piece at

http://www.openstreetmap.org/#map=16/45.1965/6.6216

on the A43, westbound, taking the exit towards Modane, the following output is produced:

debug:navit:maneuver_required2:enter 0x2076ef0 0x1f722c0 0x7fffb04ea7d8
debug:navit:maneuver_required2:- Examining allowed way: highway_land (null) A 43, delta=-3
debug:navit:maneuver_required2:- Examining allowed way: highway_land (null) A 43, delta=-3
debug:navit:maneuver_required2:- Examining allowed way: highway_land (null) A 43, delta=-3
debug:navit:maneuver_required2:- Examining allowed way: highway_land (null) A 43, delta=-3
debug:navit:maneuver_required2:A 43 (null) -> (null) (null): yes: motorway interchange (multiple motorways)

As you can see, we are getting four copies of the same way – same road name, same bearing.

This was tested with r6040, the bug has been around for quite a while.

The number of duplicates is inconsistent: I am getting four copies of the same way here, in another place I am just getting two, whereas in yet another place things seem OK.

Duplicates are not necessarily ordered – in another case I got something like way1, way2, way1.

I have tested this on two different version of map data, one dowloaded on Oct 24, 2014 and another after March 7, 2015. Both show the same pattern (including the same number of dupes at this partiular point).

I didn't do any extra research to find out where the dupes come from – they might already be in the binfile, or the code that parses the binfile and builds the route map might return the same object multiple times. I have examined current OSM data and did not find any duplicate objects in there, thus it looks like Navit is introducing them somewhere.

It's probably not critical in master, but it is an issue in the upcoming Project HighFive?, where such cases result in incorrect announcements.

If anyone has an idea where the fault may lie, please document it here – I may be able to fix it if I know where to look.

Change History (14)

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

Forgot to add one more thing – if I click the way in question on the map and select Actions > Map Point from the menu, I get only one object. That may mean the issue is specific to the navigation map – unless the UI has extra code in place to eliminate dupes...

comment:2 Changed 5 years ago by jandegr

Hi, I had a first look at it :

  • check OSM data with JOSM : no duplicates found and it seems to be this way :

https://www.openstreetmap.org/way/142893234

  • some debugging in route_process_street_graph shows that 2 ways with OSM id 142893234 are supplied by binfile.c, which is normal since maptool splits it up at the intersection with the ramp, leading to a first conclusion that maptool nor binfile are suspected.
  • some debugging in navigation_way_init (the H5 version) shows 4 ways with that same OSM id are processed, so somewhere after route_process_street_graph we already have 3 duplicates added, since itm itself is excluded.
  • inserting the proposed debugging line in maneuver_required2 now shows the 4 copies exactly the same as already illustrated in the opening post of this ticket.

tested with a map I built myself on March 23

Last edited 5 years ago by jandegr (previous) (diff)

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

I can confirm that navigation_way_init() gets called 4 times for A43 in navigation_itm_ways_update(). Apparently the loop in navigation_itm_ways_update() returns four instances of the same way. (The later debug output from maneuver_required2() confirms all four instances refer to the same way, as they all have the same delta.)

This leads me to believe that the map passed to navigation_itm_ways_update() as graph_map already has the duplicates in it.

Last edited 5 years ago by mvglasow (2) (previous) (diff)

comment:4 follow-up: Changed 5 years ago by tryagain

IIRC, route graph has two instances of each two way street, one for each direction. That's needed for Dijkstra code to work.

Looks to be the root of the issue you're trying to debug?

Last edited 5 years ago by tryagain (previous) (diff)

comment:5 in reply to: ↑ 4 Changed 5 years ago by jandegr

Replying to https://wiki.navit-project.org/index.php/user:tryagain:

IIRC, route graph has two instances of each two way street, one for each direction. That's needed for Dijkstra code to work.

Looks to be the root of the issue you're trying to debug?

At some point I was thinking in that direction as well, but a later test shows that disabling the turn restrictions processing in route.c frees navigation.c of all duplicates, at least in this testcase. I assume similar problems could arise if traffic distortions are used

comment:6 Changed 5 years ago by tryagain

I guess these easily could be filtered by item type.

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

  • Cc http://wiki.navit-project.org/index.php/user:mvglasow (2) added

What item type would we have to filter for?

Right now in navigation_itm_ways_update() we retrieve all items of type_rg_segment from the route graph map, discard all that don't have an attr_sitem or attr_direction attribute. From the remaining items we retrieve the attr_sitem, discard all of type_street_turn_restriction_no and type_street_turn_restriction_only and process the rest. Would we filter out other sitem types? Which?

We do eliminate some ways, namely those that are identical to itm->way and itm->prev.way. If the duplicates in the underlying data are not a bug, we'd have to do duplicate elimination in navigation_itm_ways_update(), e.g. by comparing each new sitem to the list we have built so far and ignoring sitems already in the list.

comment:8 Changed 5 years ago by tryagain

As you said, these duplicates disappear when you disable turn restriction processing. So I'm assuming duplicates are actually type_street_turn_restriction_* items, and was suggesting to filter them out together with traffic distortion items.

Actually, this could be done in following two ways:

  • check if sitem type is one of unneeded types and drop it
  • check if sitem is routable in active vehicle profile (most probably check if vehicleprofile_get_roadprofile(profile, sitem->type)!=NULL)
Last edited 5 years ago by tryagain (previous) (diff)

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

Actually, navigation_itm_ways_update() already discards all sitems of type_street_turn_restriction_*, and all duplicates have proper road types as item types.

debug:navit:navigation_itm_ways_update:entering for item: ramp (null) (null)
debug:navit:navigation_itm_ways_update:- adding a highway_land item
debug:navit:navigation_itm_ways_update:- added way: highway_land A 43 (null)
debug:navit:navigation_itm_ways_update:- adding a highway_land item
debug:navit:navigation_itm_ways_update:- added way: highway_land A 43 (null)
debug:navit:navigation_itm_ways_update:- adding a highway_land item
debug:navit:navigation_itm_ways_update:- added way: highway_land A 43 (null)
debug:navit:navigation_itm_ways_update:- adding a highway_land item
debug:navit:navigation_itm_ways_update:- added way: highway_land A 43 (null)

The first line of each pair ("adding a ... item") prints sitem->type, the second one ("added way") prints the attributes of the navigation_way after navigation_way_init(w) returns.

So the item type, or anything based on it, will not help us here.

I think this boils down to the question: should the route graph map contain duplicate entries?

If not, we need to fix the code that builds the route graph map and prevent the insertion of dupes.

If dupes in the route graph map are considered correct behavior (because we need them for something), then we need to filter them out in navigation_itm_ways_update() – that won't take me long to implement, but I'd rather fix the bug than implement a workaround, thus I need to know where the bug lies.

comment:10 Changed 5 years ago by tryagain

I can't say for sure, but I don't see any reasons to have duplicate entries for the same item in route graph (besides having two one-way entries for each two way item).

So duplicates look much like a bug.

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

Where does the route graph map get built? Is that route_process_street_graph(), or is there any processing that takes place in between?

comment:12 Changed 5 years ago by tryagain

According to commentary at the beginning of route.c, route graph is built in route_graph_build().

Actual work seems indeed to be done in route_process_street_graph().

comment:13 Changed 5 years ago by jandegr

there is some deliberate cloning being done in route.c, so I just thought to taint those clones, look in the listing below for 'skipped item tainted as clone' and notice only one not tainted version of each road.

I hope futher testing goes as well as testing on the specific case.

error:navit:route_graph_flood:number of edges visited =39
error:navit:rp_get_item:rp_get_item type_rg_point
error:navit:rp_get_item:rp_get_item type_rg_point
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 1, len=124 type= rg_segment
error:navit:navigation_itm_ways_update:skipped item tainted as clone id_hi=1
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 2, len=124 type= rg_segment
error:navit:navigation_itm_ways_update:skipped item tainted as clone id_hi=1
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 3, len=124 type= rg_segment
error:navit:navigation_itm_ways_update:skipped item tainted as clone id_hi=1
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 4, len=123 type= rg_segment
error:navit:navigation_itm_ways_update:item_to_name=rg_segment, sitem=highway_land
error:navit:navigation_way_init:street name_systematic= A 43 
error:navit:navigation_way_init:OSM wayid= 142893234 
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 5, len=252 type= rg_segment
error:navit:navigation_itm_ways_update:item_to_name=rg_segment, sitem=ramp
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 6, len=0 type= rg_segment
error:navit:navigation_itm_ways_update:rejecting turn restriction no
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 7, len=630 type= rg_segment
error:navit:navigation_itm_ways_update:skipped item tainted as clone id_hi=1
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 8, len=630 type= rg_segment
error:navit:navigation_itm_ways_update:skipped item tainted as clone id_hi=1
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 9, len=630 type= rg_segment
error:navit:navigation_itm_ways_update:skipped item tainted as clone id_hi=1
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 10, len=629 type= rg_segment
error:navit:navigation_itm_ways_update:item_to_name=rg_segment, sitem=highway_land
error:navit:rp_get_item:rp_get_item vervolg
error:navit:rp_get_item:rp_get_item id_lo = 11, len=0 type= rg_segment
error:navit:navigation_itm_ways_update:rejecting turn restriction only
error:navit:rp_get_item:rp_get_item vervolg
error:navit:maneuver_required2:- Examining allowed way: ramp (null) (null), delta=8
error:navit:maneuver_required2:- Examining allowed way: highway_land (null) A 43, delta=-3

if somebody wants to test the duplicate tainting and skipping :

https://github.com/navit-gps/navit/commit/9367b3566542ec57cce60f65f87b128967e26dc5

Last edited 5 years ago by jandegr (previous) (diff)

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

  • Resolution set to fixed
  • Status changed from new to closed

Fixed in commit https://github.com/mvglasow/navit/commit/7009b22a01ecad14a9486f5e50b1e144a5e016b5 which will be merged into trunk as part of HighFive?.

Since apparently the duplicates are there for a reason (has to do with turn restrictions), I had to recognize and filter them out. I have implemented a heuristic method of detecting and eliminating duplicates, which works based on item type, names and bearing (the criteria can still be tweaked as needed).

This approach has the beauty of handling other kinds of duplicates as well – for example, two overlapping maps generated from different planet.osm versions. It would be resilient to changed way IDs (which may occur when ways are split or merged), as long as the highway, name and ref tags as well as the bearing following the maneuver remain unchanged. I haven't tested this with overlapping maps – things will likely improve in some cases but not in all, and more cases could be caught by tweaking the criteria further.

I'm closing this ticket, as this issue has no implications on SVN trunk and is fixed in HighFive?.

Last edited 5 years ago by mvglasow (2) (previous) (diff)
Note: See TracTickets for help on using tickets.