[PATCH v2] - fix routing problems caused by way's bbox being too large
v2 - added some assertions to catch out of bound line start coordinates - Increased size of line bbox - reduced size of polygon bbox. I can process the whole of the UK with this patch without errors - please test this on as much map data as possible and report any assertions or SEVERE messages. The reduction in size of the polygon bbox could possibly make a difference to some large polygons (could this help with the sea areas?) ------ Ok, I think I know what's been going wrong with some people's maps where the routing goes zig-zaggy when the way is longish. However, it's not the number of points in the way or even the length of the way that's wrong. It's because the bounding box becomes sufficiently large that it causes the line to be split by the LineSizeSplitterFilter. This ancient bit of code splits the line so that it doesn't have a bigger bounding box than it thinks is acceptable. Well, that may be OK for plain lines but for routable stuff like roads, it's bad news because there's no node between the two parts of the split line. If, by chance, the point at where the way was split was actually a node anyway, it probably worked OK but for other points, anything could happen! So the attached patch checks the way's bounding box earlier on when it's doing all that boring way size/arc size/node count checking and if the BB gets too large it snips the way in the accustomed fashion. Anyway, please try the attached patch and see if it works OK - (no new bad routing, no assertions, etc.) Bloody hell, another long evening spent hacking mkgmap...
Mark, (Right after I compiled a map with your v1 patch, a 2nd version shows up...) If the map does not complain in any way (i.e. no assertions), does that mean I don't hit the bbox problem? (Your patch v2 is now included in my mkgmap, so I'll test it for a bit next days). Valentijn Mark Burton schreef:
v2 - added some assertions to catch out of bound line start coordinates - Increased size of line bbox - reduced size of polygon bbox. [...]
Hi Valentijn,
(Right after I compiled a map with your v1 patch, a 2nd version shows up...) If the map does not complain in any way (i.e. no assertions), does that mean I don't hit the bbox problem?
Yes, if the map builds OK with no assertions or SEVERE messages (that were not being produced before) then it indicates that any large bboxes that may be in the map have been split successfully. Obviously, you also need to check that nothing terrible has happened to the routing when used on a real GPS.
(Your patch v2 is now included in my mkgmap, so I'll test it for a bit next days).
Thanks. Mark
On Tue, Nov 03, 2009 at 02:48:14PM +0000, Mark Burton wrote:
I can process the whole of the UK with this patch without errors - please test this on as much map data as possible and report any assertions or SEVERE messages.
Geofabrik's finland.osm.bz2 from this morning processed fine. The mkgmap.log.0 (with the patch) and mkgmap.log.1 (without) are of the same size, and after grepping away the noise, the same three (already fixed) errors remain. I did not test the map in a device yet. Should I?
The reduction in size of the polygon bbox could possibly make a difference to some large polygons (could this help with the sea areas?)
I have not enabled the generation of sea polygons. Marko
Hi Marko,
Geofabrik's finland.osm.bz2 from this morning processed fine. The mkgmap.log.0 (with the patch) and mkgmap.log.1 (without) are of the same size, and after grepping away the noise, the same three (already fixed) errors remain.
Good.
I did not test the map in a device yet. Should I?
That would be good if you can.
The reduction in size of the polygon bbox could possibly make a difference to some large polygons (could this help with the sea areas?)
I have not enabled the generation of sea polygons.
I don't generate sea polygons either but it occurred to me that they could be big enough to be influenced by the bug I fixed. Perhaps someone will see if it has made a difference. Cheers, Mark
On Tue, Nov 03, 2009 at 08:05:43PM +0000, Mark Burton wrote:
I did not test the map in a device yet. Should I?
That would be good if you can.
I just did, testing the bicycle route to Kuortti that I mentioned in http://wiki.openstreetmap.org/wiki/Mkgmap/routing/issues#Bad_bicycle_routing a couple of months ago. It still makes the detour. It is most likely an issue with Garmin's routing algorithm, not with the map. Marko
Hi Marko,
I just did, testing the bicycle route to Kuortti that I mentioned in http://wiki.openstreetmap.org/wiki/Mkgmap/routing/issues#Bad_bicycle_routing a couple of months ago. It still makes the detour. It is most likely an issue with Garmin's routing algorithm, not with the map.
Yes, but at least it didn't obviously break anything. That's good. Cheers, Mark
Hi Mark,
I just did, testing the bicycle route to Kuortti that I mentioned in http://wiki.openstreetmap.org/wiki/Mkgmap/routing/issues#Bad_bicycle_routing a couple of months ago. It still makes the detour. It is most likely an issue with Garmin's routing algorithm, not with the map.
Yes, but at least it didn't obviously break anything. That's good.
Indeed. I should perhaps have stated it more explicitly. On the other hand, routes to central Helsinki are broken ("route calculation error"), with or without the patch, for foot and bicycle but not car. It is probably due to broken map data. I remember a similar issue several months ago. I will save the source files, so that I can investigate if the problem persists with tomorrow's dump. Marko
Mark Burton wrote:
v2 - added some assertions to catch out of bound line start coordinates - Increased size of line bbox - reduced size of polygon bbox.
I can process the whole of the UK with this patch without errors - please test this on as much map data as possible and report any assertions or SEVERE messages.
The reduction in size of the polygon bbox could possibly make a difference to some large polygons (could this help with the sea areas?)
------
Ok, I think I know what's been going wrong with some people's maps where the routing goes zig-zaggy when the way is longish. However, it's not the number of points in the way or even the length of the way that's wrong.
It's because the bounding box becomes sufficiently large that it causes the line to be split by the LineSizeSplitterFilter. This ancient bit of code splits the line so that it doesn't have a bigger bounding box than it thinks is acceptable. Well, that may be OK for plain lines but for routable stuff like roads, it's bad news because there's no node between the two parts of the split line. If, by chance, the point at where the way was split was actually a node anyway, it probably worked OK but for other points, anything could happen!
So the attached patch checks the way's bounding box earlier on when it's doing all that boring way size/arc size/node count checking and if the BB gets too large it snips the way in the accustomed fashion.
Anyway, please try the attached patch and see if it works OK - (no new bad routing, no assertions, etc.)
Bloody hell, another long evening spent hacking mkgmap...
I have the problem that with the patch applied the mdr creation breaks (on Austria and Alps from Geofabrik)! Without the patch, this error does not occur! Otherwise I could not find any differences to patch v1 (though filesize is different on about every 5th tile) D:\Garmin\mkgmap_680>REM austria at 6365 this is run35 22:14:14 Regions for map: HALL INNSBRUCK-LAND KUFSTEIN LINDAU (BODENSEE) ROSENHEIM SALZBURG SANKT GALLEN SCHWAZ TIROL VORARLBERG Exception in thread "main" java.lang.AssertionError: deltaLong = 64621 at uk.me.parabola.imgfmt.app.trergn.MapObject.setDeltaLong(MapObject.java:136) at uk.me.parabola.imgfmt.app.trergn.RGNFileReader.fetchPointsCommon(RGNFileReader.java:117) at uk.me.parabola.imgfmt.app.trergn.RGNFileReader.pointsForSubdiv(RGNFileReader.java:77) at uk.me.parabola.imgfmt.app.map.MapReader.pointsForLevel(MapReader.java:107) at uk.me.parabola.mkgmap.combiners.MdrBuilder.addPoints(MdrBuilder.java:170) at uk.me.parabola.mkgmap.combiners.MdrBuilder.onMapEnd(MdrBuilder.java:113) at uk.me.parabola.mkgmap.main.Main.endOptions(Main.java:361) at uk.me.parabola.mkgmap.CommandArgsReader.readArgs(CommandArgsReader.java:124) at uk.me.parabola.mkgmap.main.Main.main(Main.java:122) 22:16:35 Bzw fuer alps: D:\Garmin\mkgmap_680>REM alps alp 6528 this is run40 22:20:19 Regions for map: AIN HAUTE SAVOIE HAUTE-SAVOIE HAUTE-SAVOIE-GROISY IS?RE RHE`NE-ALPES SAVOIE Exception in thread "main" java.lang.AssertionError: deltaLong = 65331 at uk.me.parabola.imgfmt.app.trergn.MapObject.setDeltaLong(MapObject.java:136) at uk.me.parabola.imgfmt.app.trergn.RGNFileReader.fetchPointsCommon(RGNFileReader.java:117) at uk.me.parabola.imgfmt.app.trergn.RGNFileReader.pointsForSubdiv(RGNFileReader.java:77) at uk.me.parabola.imgfmt.app.map.MapReader.pointsForLevel(MapReader.java:107) at uk.me.parabola.mkgmap.combiners.MdrBuilder.addPoints(MdrBuilder.java:170) at uk.me.parabola.mkgmap.combiners.MdrBuilder.onMapEnd(MdrBuilder.java:113) at uk.me.parabola.mkgmap.main.Main.endOptions(Main.java:361) at uk.me.parabola.mkgmap.CommandArgsReader.readArgs(CommandArgsReader.java:124) at uk.me.parabola.mkgmap.main.Main.main(Main.java:122)
------------------------------------------------------------------------
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Felix,
I have the problem that with the patch applied the mdr creation breaks (on Austria and Alps from Geofabrik)! Without the patch, this error does not occur!
These Austria and Alps files, what created them? Was it you using mkgmap with this latest patch? Or did they come from somewhere else? Cheers, Mark
Mark Burton wrote:
Hi Felix,
I have the problem that with the patch applied the mdr creation breaks (on Austria and Alps from Geofabrik)! Without the patch, this error does not occur!
These Austria and Alps files, what created them? Was it you using mkgmap with this latest patch? Or did they come from somewhere else?
ups sorry, me in one go (as susual from geofabrik - download date 1.11). I did not try out other countries yet, suppose they will fail too. With problems on index creation appearing quite often I really think about using a stable mkgmap version for the index creation, and another one for the .img creation... But then I wouldn't find the bugs anymore...
Cheers,
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Felix,
ups sorry, me in one go (as susual from geofabrik - download date 1.11). I did not try out other countries yet, suppose they will fail too. With problems on index creation appearing quite often I really think about using a stable mkgmap version for the index creation, and another one for the .img creation... But then I wouldn't find the bugs anymore...
Hold on, don't be so hasty to tell yourself off! The patch may not be right. I am having doubts about that assertion so standby for further news...
Hi Felix, Please apply the attached patch to mkgmap - keep the v2 bbox patch as well - try processing those Austria and Alps files again and let me know what happens. thanks
Yeah that fixed it (I'm still calculating on Alps, but pretty sure it'll pass too - otherwise I will follow it up). Mark Burton wrote:
Hi Felix,
Please apply the attached patch to mkgmap - keep the v2 bbox patch as well - try processing those Austria and Alps files again and let me know what happens.
thanks
------------------------------------------------------------------------
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Felix,
Yeah that fixed it (I'm still calculating on Alps, but pretty sure it'll pass too - otherwise I will follow it up).
Very good, so that's a sign extension issue in the code that reads img files. It just so happens that the assertions I added as part of my current effort detected the problem. I will commit the fix. Cheers, Mark
I've committed this patch as no one has reported it breaking any routing. I have tested it on mapsource, etrex and nuvi with not problems observed.
participants (4)
-
Felix Hartmann -
Mark Burton -
Marko Mäkelä -
Valentijn Sessink