Behave gracefully when supplied with overlapping binfile maps.

[aerostitch]

Issue migrated from trac ticket # 1046

component: core | priority: minor | keywords: multi maps, binfile, routing

2012-05-29 13:51:15: tryagain created the issue

---

Android map download feature allows user to download map pieces by country or, for some countries, region.

Currently, if user have downloaded more than one map, he will be hit with strange navigation behavior (a misleading message would be spoken at each crossing) and duplicate search results. Other unwanted results may be seen.

Binfiles downloaded from the map server consist of tiles extracted from the planet binfile. So even if two map areas requested from the map server do not visually overlap, they usually would contain some duplicated items belonging to tiles of few top levels.

Similar problem was discussed at #1039, but that one was caused by a different case, the same map file were used twice by the navit android port.

I don't think we have any chance to compose a perfectly working map if user would have randomly downloaded parts built from different planet.osm versions.

But if we put additional assumption that all maps are built nearly at the same time, I see some options to consider.

For example, we could remember osm ids of all objects proccessed from the mapset and skip duplicates. This one seems to be too memory hungry and still doesn't solve the case when we have two different versions of the same object.

Another way is to remember only tile names processed and skip whole duplicate tiles. This seems to be the best solution. But it will break situation if user has intentionally overlapping binfiles of different origins. For example, usual osm based binfile and one built from the third party POI data. So we need some way to mark binfile origin. Additional

It would be useful to have some warning if user has binfiles (to be precise, tiles) of same origin and [significantly] different timestamps.

I think, maptool also could be modified to produce all tiles with same timestamp so we can always be sure if two tiles are the same.

[aerostitch]

2012-12-31 04:52:00: @mvglasow changed title from Bheave gracefully when supplied with overlapping binfile maps. to Behave gracefully when supplied with overlapping binfile maps.

[aerostitch]

2012-12-31 04:52:00: @mvglasow commented

---

As a quick fix, how about simply suppressing the superfluous turn instructions?

If I get it correctly, the problem occurs whenever

• two or more binfiles containing the same tile are loaded
• the user passes a node where one way ends and another one begins, but the road just continues (which happens every time an OSM attribute such such as bridge, tunnel, maxspeed etc. changes)

Such cases should be fairly easy to detect because of the following:

• The point at which the maneuver occurs is the endpoint of all ways of which it is a member.
• The list of ways involved contain exactlys two OSM IDs.

If such a case is found, just eliminate the turn instructions from the list and examine the next one.

This issue gets more and more serious because map files are getting too big for certain boundaries. For example, a map rectangle comprising the entire EU exceeds 4 GB in size and no longer fits on a FAT32 volume (which is the USB storage format on most Android devices).

[aerostitch]

2013-01-01 02:11:51: tryagain commented

---

Hi!

Good idea, but it would be better to analyse for duplicate edges while the routing graph is built, to reduce its complexity. Having overlapped tiles currently has heavy perfomance impact.

AFAIK osm wayid info is skipped from the routing graph while it's built, so comparing by osmway id won't be an option at that stage.

But fortunately, here's no sense to have totally identical (by lengts, access flags, endpoints) edges in the roting graph, regardless if they have same OSM Wayids or not. So we can just skip such edges while the graph is built.

As a workaround (which might be a primary solution) we have a way to split the map region into pieces not having duplicate tiles. At http://maps.test.navit-project.org you can download your selected region as a set of map files each not exceeding given size limit.

tryagain

[aerostitch]

2013-01-01 05:19:11: tryagain changed priority from major to minor

[aerostitch]

2013-01-01 05:19:11: tryagain commented

---

The routing and navigational issues are fixed with 5334

We still have duplicate results in POI search, extra resources are required to display overlapped areas by graphics code.

Are there any other known issues?

I feel we can lower the priority to minor now.

[aerostitch]

2013-01-03 12:23:46: @mvglasow commented

---

Both approaches look good to me (in fact, I had an afterthought of reducing the route graph before building, as there are some corner cases which my suggestion would not have caught).

However, after upgrading to 5334 Navit stopped calculating routes altogether (tried on short routes within the city). When I closed Navit, downgraded to 5333 and restarted, I got a route within a few seconds.

There seems to be some bug in 5334...

[aerostitch]

2013-01-03 13:27:45: tryagain commented

---

Ups.

Can you please specify your map details (which area, where you have get it from, how is it old, do you use one or more maps at the same time) and platform?

Does turning the Route Graph map on sched some light on what's going wrong (attach a screenshot of a short route not being computed together with its coordinates or osm id of some way on it)?

I have retested it with current svn navit/android (self built), with default config. It routes for me well.

[aerostitch]

2013-01-03 13:27:45: tryagain

[aerostitch]

2013-01-03 13:27:45: tryagain

[aerostitch]

2013-01-06 11:10:38: fre.labrosse@googlemail.com commented

---

Replying to [comment:4 http://wiki.navit-project.org/index.php/user:mvglasow]:

However, after upgrading to 5334 Navit stopped calculating routes altogether (tried on short routes within the city). When I closed Navit, downgraded to 5333 and restarted, I got a route within a few seconds.

Just drove about 150 miles with 5337 and did get random failures at routing. I started with a route, which then was lost (I was driving on the correct road, the route just got lost). It then took a long time (many miles) to get a route again. Navit was retrying every few seconds but failing. This happened several times and seemed random.

I'm not sure but I think I saw that several times it got a route while the GPS was positioning me on a small side road.

Fred

[aerostitch]

2013-01-08 06:47:54: @mvglasow commented

---

@tryagain: I'll try to reproduce, but I encountered the error while on vacation, 1600 km away from home, and have since returned home. I'll see.

@fre labrosse: In the case you described, could it be that from time to time Navit determined that your position was slightly next to the road rather than on it? This may happen if the GPS signal is weak (I've had it a couple of times) and is an unrelated issue. I've opened #1093 for that.

[aerostitch]

2013-01-08 08:09:24: fre.labrosse@googlemail.com commented

---

Replying to [comment:8 http://wiki.navit-project.org/index.php/user:mvglasow]:

@fre labrosse: In the case you described, could it be that from time to time Navit determined that your position was slightly next to the road rather than on it? This may happen if the GPS signal is weak (I've had it a couple of times) and is an unrelated issue. I've opened #1093 for that.

I don't think it was because (1) navit was putting me on the road at these points (when it was failing to compute a route and (2) even when I'm off the road, navit gives me a route when it succeeds (straight to nearest road and then from there). It was not taking a long time to find a route, it was failing. I'll try to reproduce that on the same computer at some point.

[aerostitch]

2013-01-08 22:12:50: tryagain commented

---

Hi!

There's actually a bug in 5334, which makes navigation broken when you have a route built over multiple overlapped maps.

Problem happens only when you navigate on the road having a duplicate and it looks like navit just looses the route and tries to build it over and over again. And it doesnt reproduceable with demo vehicle.

I'll revert the change as soon as I get to my dev environment (tonight), unless I get some fresh idea how to fix it by that time.

Sorry for inconvenience i have caused.

tryagain.

[aerostitch]

2013-01-09 08:15:06: @mvglasow commented

---

Just did some quick tests (still on 5333) with a split binfile containing the entire EU, things look good. Plus, the test download site has the benefit of actually displaying the download link so I can bookmark it and download the same map again.

Splitting the map is probably the best way to go - no data duplication and no waste of precious storage space; overlapping maps are kind of ugly and the only reason I had for using them is that a single binfile of all countries I'm interested in is too large.

[aerostitch]

2013-01-09 13:39:37: tryagain commented

---

I have reverted back 5334 with 5338, so now navigation should work as before, you would get excessive insructions if you have more than one overlapped map.

The issue was caused by the fact that route_set_position/route_set_position_from_tracking would use a closest item from the random map, and that selected item could be skipped from the route graph. In the latter case route gets rebuild over and over again.

Function route_set_position seems to be easy to fix by dropping found streets which are not in route graph if we can find the one which belongs it.

Function route_set_position_from_tracking seems to be more complex case, because it depends on tracking code which knows nothing about route graph.

I think it would be a possible solution to make route_segment_data possible to store more than one item re at a time, thus reducing graph size and filtering out unnecesary announcements while keeping ability to continue from any of item.

It looks to be smart idea to lookup route path data for the closest street. And unless we gone more than threshodl, don't even touch other sources. Same for tracking.

tryagain.

[aerostitch]

2013-07-28 04:23:45: usul

[aerostitch]

2013-07-28 04:23:45: usul commented

---

Needs to be reviewed for current SVN and IMHO fixed.

[aerostitch]

2013-12-19 14:51:19: fre.labrosse@googlemail.com changed severity from * to normal*

[aerostitch]

2013-12-19 14:51:19: fre.labrosse@googlemail.com commented

---

Hi,

I updated to svn a couple of days ago and downloaded maps for the UK and France yesterday. I then tried it on a short local route only to find that the same old behaviour of announcing many turns when there are none is still there. I thought this was fixed?

Fred

[aerostitch]

2015-10-14 05:17:59: @mvglasow commented

---

Project HighFive, which got merged a few months back, should have fixed this for cases where there's a precise overlap. When two segments have the same endpoint and the same bearing at that point, they are treated as one.

What remains problematic are cases where the overlapping area has two different map versions, with road layout differing slightly due to edits. This would be hard to filter out, though.

[aerostitch]

2017-12-02 04:08:44: @jkoan

[aerostitch]

2017-12-02 04:08:44: @jkoan commented

---

This ticket was pushed back in order to bring 0.5.1 out soon.