[PATCH] make gps report correct exit when routing through roundabouts
As discussed yesterday, the gps sometimes tells you to leave the roundabout at an earlier exit than it should. I believe that whether this happens or not is influenced by the angle at which roads are attached to the roundabout or something related to the angles between the roundabout segments. For example, a roundabout with 4 points, each point having a road, will probably work OK if the roads "point" pretty much at the centre of the roundabout, like this: | --@-- | But if the roads are more like this: -- -- @ -- -- the gps is likely to get the exit count wrong. The attached patch "frigs" roundabouts by adding an extra point between each pair of adjacent nodes. The extra points are positioned "outside" of the line joining the two nodes. The effect is to make roundabouts "rounder". Unfortunately, it also makes them ugly as the frigging is being done by a dumb computer with little aesthetic capability. However, the good news is that it appears to make the routing instructions specify the correct exit now. YMMV If interested, please try this out and report success/failure. In particular, it would be good to know if it makes roundabouts that previously were OK, bad. The patch is for the current "nod" branch. Cheers, Mark
If you can tell me the necessary incantations to apply a patch I'll gladly try this out. Paul Mark Burton wrote:
As discussed yesterday, the gps sometimes tells you to leave the roundabout at an earlier exit than it should. I believe that whether this happens or not is influenced by the angle at which roads are attached to the roundabout or something related to the angles between the roundabout segments.
For example, a roundabout with 4 points, each point having a road, will probably work OK if the roads "point" pretty much at the centre of the roundabout, like this:
| --@-- |
But if the roads are more like this:
-- -- @ -- --
the gps is likely to get the exit count wrong.
The attached patch "frigs" roundabouts by adding an extra point between each pair of adjacent nodes. The extra points are positioned "outside" of the line joining the two nodes. The effect is to make roundabouts "rounder". Unfortunately, it also makes them ugly as the frigging is being done by a dumb computer with little aesthetic capability.
However, the good news is that it appears to make the routing instructions specify the correct exit now. YMMV
If interested, please try this out and report success/failure. In particular, it would be good to know if it makes roundabouts that previously were OK, bad.
The patch is for the current "nod" branch.
Cheers,
Mark
------------------------------------------------------------------------
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
If you can tell me the necessary incantations to apply a patch I'll gladly try this out.
Save the patch to a file (roundabout-frig.patch) Go into the top-level directory of the mkgmap source (nod branch) Copy or move patch file to same directory (or just give pathname to file when you run patch). Patch with: patch -p1 < roundabout-frig.patch Patch should report successful patching of StyledConverter.java Cheers, Mark
Ok then. Prior to patching I had no problem running mkgmap against the files for england created by splitter (5 in total). After patching it fails on the second with the error below. The remaining 4 are fine In between runs I ran "ant clobber", then patched, and then "ant dist". The file that gives the error has the following <bounds minlat='49.526367' minlon='-1.010742' maxlat='51.459961' maxlon='2.065430'/> which includes the bottom half of London. At the moment I don't have time to narrow it down any further Paul Mark Burton wrote:
If you can tell me the necessary incantations to apply a patch I'll gladly try this out.
Save the patch to a file (roundabout-frig.patch)
Go into the top-level directory of the mkgmap source (nod branch)
Copy or move patch file to same directory (or just give pathname to file when you run patch).
Patch with:
patch -p1 < roundabout-frig.patch
Patch should report successful patching of StyledConverter.java
Cheers,
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
bos@anonymous:~/Maps/mkgmap/mkgmap-r877-nod/dist> java -Xmx2048M -jar mkgmap.jar --route --latin1 --gmapsupp 63240002.osm Exception in thread "main" java.lang.IllegalArgumentException at uk.me.parabola.imgfmt.app.BitWriter.putn(BitWriter.java:89) at uk.me.parabola.imgfmt.app.trergn.LinePreparer.makeBitStream(LinePreparer.java:123) at uk.me.parabola.imgfmt.app.trergn.Polyline.write(Polyline.java:87) at uk.me.parabola.imgfmt.app.trergn.RGNFile.addMapObject(RGNFile.java:96) at uk.me.parabola.imgfmt.app.map.Map.addMapObject(Map.java:229) at uk.me.parabola.mkgmap.build.MapBuilder$LineAddFilter.doFilter(MapBuilder.java:615) at uk.me.parabola.mkgmap.build.LayerFilterChain.doFilter(LayerFilterChain.java:57) at uk.me.parabola.mkgmap.filters.RemoveEmpty.doFilter(RemoveEmpty.java:52) at uk.me.parabola.mkgmap.build.LayerFilterChain.doFilter(LayerFilterChain.java:57) at uk.me.parabola.mkgmap.filters.LineSplitterFilter.doFilter(LineSplitterFilter.java:60) at uk.me.parabola.mkgmap.build.LayerFilterChain.doFilter(LayerFilterChain.java:57) at uk.me.parabola.mkgmap.filters.SmoothingFilter.doFilter(SmoothingFilter.java:80) at uk.me.parabola.mkgmap.build.LayerFilterChain.doFilter(LayerFilterChain.java:57) at uk.me.parabola.mkgmap.build.LayerFilterChain.startFilter(LayerFilterChain.java:75) at uk.me.parabola.mkgmap.build.MapBuilder.processLines(MapBuilder.java:509) at uk.me.parabola.mkgmap.build.MapBuilder.makeSubdivision(MapBuilder.java:331) at uk.me.parabola.mkgmap.build.MapBuilder.makeMapAreas(MapBuilder.java:266) at uk.me.parabola.mkgmap.build.MapBuilder.makeMap(MapBuilder.java:130) at uk.me.parabola.mkgmap.main.MapMaker.makeMap(MapMaker.java:87) at uk.me.parabola.mkgmap.main.MapMaker.makeMap(MapMaker.java:53) at uk.me.parabola.mkgmap.main.Main.processFilename(Main.java:150) at uk.me.parabola.mkgmap.CommandArgs$Filename.processArg(CommandArgs.java:329) at uk.me.parabola.mkgmap.CommandArgs.readArgs(CommandArgs.java:119) at uk.me.parabola.mkgmap.main.Main.main(Main.java:91)
Hi Paul, Thanks for the report - sorry it failed. Robert (or anyone else that knows), is this exception caused by points being too close together? The code in BitWriter.java that's barfing is: public void putn(int bval, int nb) { int val = bval & ((1<<nb) - 1); int n = nb; // We need to be able to deal with more than 24 bits, but now we can't yet if (n >= 24) throw new IllegalArgumentException(); If so, what's the minimum distance between points? If not, can you say why it needs 24 bits or more? Cheers, Mark
On Feb 11, 2009, at 16:17, Mark Burton wrote:
Robert (or anyone else that knows), is this exception caused by points being too close together? The code in BitWriter.java that's barfing is:
public void putn(int bval, int nb) { int val = bval & ((1<<nb) - 1); int n = nb;
// We need to be able to deal with more than 24 bits, but now we can't yet if (n >= 24) throw new IllegalArgumentException();
If so, what's the minimum distance between points?
If not, can you say why it needs 24 bits or more?
I don't know the BitWriter code, or why the limit of 24 bits. These bit streams come from LinePreparer, and each putn should correspond to one latitude or longitude delta between adjacent coordinates in a polyline. 24 bits seems quite large for a delta. A large delta should correspond to a large distance between coordinates, but since 2**24 map units is 360 degrees, this limit shouldn't really be reached. Perhaps it's some bug close to longitude 0? I think mkgmap puts out some debugging info from the LinePreparer: try java -Dlog.config=resources/logging.properties Cheers Robert
On Feb 11, 2009, at 16:51, Robert Vollmert wrote:
On Feb 11, 2009, at 16:17, Mark Burton wrote:
Robert (or anyone else that knows), is this exception caused by points being too close together? The code in BitWriter.java that's barfing is:
public void putn(int bval, int nb) { int val = bval & ((1<<nb) - 1); int n = nb;
// We need to be able to deal with more than 24 bits, but now we can't yet if (n >= 24) throw new IllegalArgumentException();
If so, what's the minimum distance between points?
If not, can you say why it needs 24 bits or more?
I don't know the BitWriter code, or why the limit of 24 bits.
These bit streams come from LinePreparer, and each putn should correspond to one latitude or longitude delta between adjacent coordinates in a polyline. 24 bits seems quite large for a delta.
A large delta should correspond to a large distance between coordinates, but since 2**24 map units is 360 degrees, this limit shouldn't really be reached.
Perhaps it's some bug close to longitude 0?
Something along these lines might help (doesn't as is, but no time): Index: src/uk/me/parabola/imgfmt/app/trergn/LinePreparer.java =================================================================== --- src/uk/me/parabola/imgfmt/app/trergn/LinePreparer.java (revision 833) +++ src/uk/me/parabola/imgfmt/app/trergn/LinePreparer.java (working copy) @@ -200,8 +200,11 @@ continue; } - int dx = lon - lastLong; - int dy = lat - lastLat; + // calculate normalized differences + int dx = (lon - lastLong) % (1 << (24-shift)) + - (1 << (23-shift)); + int dy = (lat - lastLat) % (1 << (24-shift)) + - (1 << (23-shift)); lastLong = lon; lastLat = lat; Cheers Robert
On Feb 11, 2009, at 17:19, Robert Vollmert wrote:
Something along these lines might help (doesn't as is, but no time):
This compiles, at least, and probably does what I want: Index: src/uk/me/parabola/imgfmt/app/trergn/LinePreparer.java =================================================================== --- src/uk/me/parabola/imgfmt/app/trergn/LinePreparer.java (revision 877) +++ src/uk/me/parabola/imgfmt/app/trergn/LinePreparer.java (working copy) @@ -200,8 +200,12 @@ continue; } - int dx = lon - lastLong; - int dy = lat - lastLat; + // calculate normalized differences + int max = 1 << (24-shift); + int dx = (lon - lastLong) % (1 << (24-shift)); + if (dx >= max/2) dx -= max/2; + int dy = (lat - lastLat) % (1 << (24-shift)); + if (dy >= max/2) dy -= max/2; lastLong = lon; lastLat = lat;
0> In article <28313007-F338-4CF6-ACAD-FB46DC1DC800@gmx.net>, 0> Robert Vollmert <URL:mailto:rvollmert-lists@gmx.net> ("Robert") wrote: Robert> This compiles, at least, and probably does what I want: Robert> + // calculate normalized differences Robert> + int max = 1 << (24-shift); Robert> + int dx = (lon - lastLong) % (1 << (24-shift)); Robert> + if (dx >= max/2) dx -= max/2; Robert> + int dy = (lat - lastLat) % (1 << (24-shift)); Robert> + if (dy >= max/2) dy -= max/2; Robert> Robert> lastLong = lon; Robert> lastLat = lat; I'd suggest helping the compiler by putting that (1 << (24-shift)) into a (local) constant. Actually, using the fact that a Java int is 32-bit and signed, you can do something like (untested) /-------- | final int offset = 8+shift; | int dx = (lon - lastLong) << offset >> offset; | ind dy = (lat - lastLat) << offset >> offset; \-------- to truncate and sign-extend those values. This approach will probably run faster on most hardware, as I've eliminated those conditionals. I've not read and understood enough of the code to work out whether the sign extension is really required; if not, a simple AND mask may be sufficient.
Here's a new version of this patch. What it does is an ugly hack but if it fixes the problem without hideous side effects it will probably serve until some better way of solving the problem is devised. It is no longer enabled by default, you need to specify the --frig-roundabouts option. By default the "frig factor" (influences how far the new points are away from the centre of the roundabout) is set to 0.25. You can specify a different value as the option value: --frig-roundabouts=0.1 Large values tend to make the roundabout uglier so it would be worth experimenting to see what the minimum frig factor is that will stop the gps from reporting the wrong exit. You can also enable frigging for an individual roundabout by tagging the OSM XML with the "mkgmap:frig_roundabout" tag which can either be set to a valid (floating point) number to specify the frig factor or just some other string that will make it use the default frig factor. This patch also avoids putting in new points if the new point would be less than 5 or more than 100 metres from the adjacent points. This may stop the exception reported by Paul, but probably not. This patch replaces the version from earlier today and is for the current nod branch in SVN. As always, feedback is appreciated. Cheers, Mark
I have bad news and good news. The bad news is that the second patch also failed. The good news is that I *"think"* I have found the data that causes the problem. Call me sad if you want but I had a spare hour (not) so using osmosis I started splitting the tile giving the error into 4 quarters. I would run each of these and see if there were errors. I then split the quarter with errors and repeated the process until I was left with the attached file. In the bottom left quarter is a tiny roundabout. If you just move the north node northwards and the south road southwards a couple of feet then the tile runs without errors. As it's such a minimal change I have already applied this to the live map so this should be on the Geofabrik mirrir tomorrow. I'm out all day tomorrow so won't be able to test this until the evening but I'll report back as soon as possible. Paul P.S. This runs without the --frig-roundabouts option and runs on the unpatched code from r877 Mark Burton wrote:
Here's a new version of this patch.
What it does is an ugly hack but if it fixes the problem without hideous side effects it will probably serve until some better way of solving the problem is devised.
It is no longer enabled by default, you need to specify the --frig-roundabouts option. By default the "frig factor" (influences how far the new points are away from the centre of the roundabout) is set to 0.25. You can specify a different value as the option value: --frig-roundabouts=0.1
Large values tend to make the roundabout uglier so it would be worth experimenting to see what the minimum frig factor is that will stop the gps from reporting the wrong exit.
You can also enable frigging for an individual roundabout by tagging the OSM XML with the "mkgmap:frig_roundabout" tag which can either be set to a valid (floating point) number to specify the frig factor or just some other string that will make it use the default frig factor.
This patch also avoids putting in new points if the new point would be less than 5 or more than 100 metres from the adjacent points. This may stop the exception reported by Paul, but probably not.
This patch replaces the version from earlier today and is for the current nod branch in SVN.
As always, feedback is appreciated.
Cheers,
Mark
------------------------------------------------------------------------
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
The good news is that I *"think"* I have found the data that causes the problem. Call me sad if you want but I had a spare hour (not) so using osmosis I started splitting the tile giving the error into 4 quarters. I would run each of these and see if there were errors. I then split the quarter with errors and repeated the process until I was left with the attached file. In the bottom left quarter is a tiny roundabout. If you just move the north node northwards and the south road southwards a couple of feet then the tile runs without errors.
Nicely tracked down. The northmost and the eastmost points on that roundabout are about 5m apart and routing nodes have to be more than 5.4m apart. ..Steve
On Feb 11, 2009, at 23:55, Steve Ratcliffe wrote:
The good news is that I *"think"* I have found the data that causes the problem. Call me sad if you want but I had a spare hour (not) so using osmosis I started splitting the tile giving the error into 4 quarters. I would run each of these and see if there were errors. I then split the quarter with errors and repeated the process until I was left with the attached file. In the bottom left quarter is a tiny roundabout. If you just move the north node northwards and the south road southwards a couple of feet then the tile runs without errors.
Nicely tracked down.
It turns out my patch above fixes the IllegalArgumentException, though I don't really know why, since the roundabout isn't really close to longitude zero. Also I don't know if it doesn't break anything else, so I'm hesitant about committing it.
The northmost and the eastmost points on that roundabout are about 5m apart and routing nodes have to be more than 5.4m apart.
Do we know why this is? I remember in the length calculation discussion that the unit of arc length was 5.4m, but we could just lie for shorter arcs. Cheers Robert
participants (5)
-
Mark Burton -
Paul -
Robert Vollmert -
Steve Ratcliffe -
Toby Speight