higher precision instead of short-arc-removal?
Hi programmers, I am still working on the improved short-arc-removal routines. I found a few more special cases, and many of them are related to the fact that we are using the rounded lat/lon values (Garmin map units). Short excurse: A map unit is a 24bit integer value, means we can separate 2^24 = 16777216 different positions on the equator. By the way, the comment in Utils.toMapUnit "A map unit is an integer value that is 1/(2^24) degrees of latitude or longitue" is wrong, we store 1/(2^23) of a value that goes from -180.0 to 180.0. Means ~ 2.39m (40075 km / 16777216) near the equator. In Berlin, the value is ~ 1.45m for lon (lat is of course the same). So, the rounding error is 0.75 to 1.2m in this area. While these errors are not important when it comes to rendering a map, they might be important when it comes to routing. In some cases I find segments of ways with two points that are very close. Imagine a nearly vertical short segment. The rounding might move one point to the left, the other to the right, so that (in map units) with deltaLat = 1 and deltaLon = 1 the calculated bearing of ~ 148 is nonsense, as the real value is e.g 178. If I got this right, the Garmin routing algo uses the bearing value. We store it (heavily rounded to 8 or fewer bits), and the comments in RouteArc.encodeCurve() say that we are not sure about the img format. I think this might also explain why short arcs cause trouble, maybe it is not the short arc itself, maybe we simply write wrong data to the img when we store roads with points that are very close to each other? If that is true, we might better try to find out what we have to write to the img instead of messing around with short arcs? If only precision is the problem: Maybe we can Coord to store the lat/lon values with 30 bits precision? Gerd -- View this message in context: http://gis.19327.n5.nabble.com/higher-precision-instead-of-short-arc-removal... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi programmers,
I am still working on the improved short-arc-removal routines. I found a few more special cases, and many of them are related to the fact that we are using the rounded lat/lon values (Garmin map units).
Short excurse: A map unit is a 24bit integer value, means we can separate 2^24 = 16777216 different positions on the equator. By the way, the comment in Utils.toMapUnit "A map unit is an integer value that is 1/(2^24) degrees of latitude or longitue" is wrong, we store 1/(2^23) of a value that goes from -180.0 to 180.0.
Means ~ 2.39m (40075 km / 16777216) near the equator. In Berlin, the value is ~ 1.45m for lon (lat is of course the same). So, the rounding error is 0.75 to 1.2m in this area. While these errors are not important when it comes to rendering a map, they might be important when it comes to routing.
In some cases I find segments of ways with two points that are very close. Imagine a nearly vertical short segment. The rounding might move one point to the left, the other to the right, so that (in map units) with deltaLat = 1 and deltaLon = 1 the calculated bearing of ~ 148 is nonsense, as the real value is e.g 178.
If I got this right, the Garmin routing algo uses the bearing value. We store it (heavily rounded to 8 or fewer bits), and the comments in RouteArc.encodeCurve() say that we are not sure about the img format.
I think this might also explain why short arcs cause trouble, maybe it is not the short arc itself, maybe we simply write wrong data to the img when we store roads with points that are very close to each other?
If that is true, we might better try to find out what we have to write to the img instead of messing around with short arcs?
If only precision is the problem: Maybe we can Coord to store the lat/lon values with 30 bits precision?
Gerd
Hi Gerd, interesting idea to increase the precision of coordinates. I sometimes thought about using "real" coordinates but using doubles instead of int seemed to be too much memory overhead. Increasing the precision to 30 bits seems to be a much better way. The crucial point is: does the higher precision really help? In the end you also have to convert the high precision coordinates to the garmin precision. At this point I guess you will have the short arcs problem again? Of course the calculation of the bearings will be better. But this will not fix an img format problem (if that exist). So what about a systematic check the encodeCurve() method first? Would it be possible to create an map where all possible headings are encoded? In this case it might be possible to find out problematic values?! WanMil
Hi WanMil, I also prefer to make sure that a correct img file is written. I have just managed to produce a routing error with the trunk version which disappears when using the mergeroads branch, even if I comment the call of mergeroads() . Next step is to find out what is changed... Gerd WanMil wrote
Hi programmers,
I am still working on the improved short-arc-removal routines. I found a few more special cases, and many of them are related to the fact that we are using the rounded lat/lon values (Garmin map units).
Short excurse: A map unit is a 24bit integer value, means we can separate 2^24 = 16777216 different positions on the equator. By the way, the comment in Utils.toMapUnit "A map unit is an integer value that is 1/(2^24) degrees of latitude or longitue" is wrong, we store 1/(2^23) of a value that goes from -180.0 to 180.0.
Means ~ 2.39m (40075 km / 16777216) near the equator. In Berlin, the value is ~ 1.45m for lon (lat is of course the same). So, the rounding error is 0.75 to 1.2m in this area. While these errors are not important when it comes to rendering a map, they might be important when it comes to routing.
In some cases I find segments of ways with two points that are very close. Imagine a nearly vertical short segment. The rounding might move one point to the left, the other to the right, so that (in map units) with deltaLat = 1 and deltaLon = 1 the calculated bearing of ~ 148 is nonsense, as the real value is e.g 178.
If I got this right, the Garmin routing algo uses the bearing value. We store it (heavily rounded to 8 or fewer bits), and the comments in RouteArc.encodeCurve() say that we are not sure about the img format.
I think this might also explain why short arcs cause trouble, maybe it is not the short arc itself, maybe we simply write wrong data to the img when we store roads with points that are very close to each other?
If that is true, we might better try to find out what we have to write to the img instead of messing around with short arcs?
If only precision is the problem: Maybe we can Coord to store the lat/lon values with 30 bits precision?
Gerd
Hi Gerd,
interesting idea to increase the precision of coordinates. I sometimes thought about using "real" coordinates but using doubles instead of int seemed to be too much memory overhead. Increasing the precision to 30 bits seems to be a much better way.
The crucial point is: does the higher precision really help? In the end you also have to convert the high precision coordinates to the garmin precision. At this point I guess you will have the short arcs problem again? Of course the calculation of the bearings will be better. But this will not fix an img format problem (if that exist). So what about a systematic check the encodeCurve() method first? Would it be possible to create an map where all possible headings are encoded? In this case it might be possible to find out problematic values?!
WanMil
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/higher-precision-instead-of-short-arc-removal... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi, that error was caused by the wrong highwayCounts (hwc)caused by short-arc-removal. The first node of way replaced another node connected to multiple roads having hwc=4. The first node is not connected to any other road. Effect of the error: More nodes with hwc=1, wrong network, but correct img file. Maybe it is really a good idea to use remove-short-arcs=0.0. I was not able to find a routing error with r2727 from the mergeroads branch using this value, while the default value 5.0 removes some small footways between roads, e.g. it routes me from Hakenweg directly to Jütlandstraße: http://www.openstreetmap.org/#map=19/53.02873/8.64524 @WanMil: Are you planning to merge back to trunk? If not, I should commit the coordPOI_v2.patch to trunk, and that would probably cause you trouble when merging. If found only small issues, e.g. the javadoc for resetHighwayCounts(). Gerd GerdP wrote
Hi WanMil,
I also prefer to make sure that a correct img file is written. I have just managed to produce a routing error with the trunk version which disappears when using the mergeroads branch, even if I comment the call of mergeroads() . Next step is to find out what is changed...
Gerd WanMil wrote
Hi programmers,
I am still working on the improved short-arc-removal routines. I found a few more special cases, and many of them are related to the fact that we are using the rounded lat/lon values (Garmin map units).
Short excurse: A map unit is a 24bit integer value, means we can separate 2^24 = 16777216 different positions on the equator. By the way, the comment in Utils.toMapUnit "A map unit is an integer value that is 1/(2^24) degrees of latitude or longitue" is wrong, we store 1/(2^23) of a value that goes from -180.0 to 180.0.
Means ~ 2.39m (40075 km / 16777216) near the equator. In Berlin, the value is ~ 1.45m for lon (lat is of course the same). So, the rounding error is 0.75 to 1.2m in this area. While these errors are not important when it comes to rendering a map, they might be important when it comes to routing.
In some cases I find segments of ways with two points that are very close. Imagine a nearly vertical short segment. The rounding might move one point to the left, the other to the right, so that (in map units) with deltaLat = 1 and deltaLon = 1 the calculated bearing of ~ 148 is nonsense, as the real value is e.g 178.
If I got this right, the Garmin routing algo uses the bearing value. We store it (heavily rounded to 8 or fewer bits), and the comments in RouteArc.encodeCurve() say that we are not sure about the img format.
I think this might also explain why short arcs cause trouble, maybe it is not the short arc itself, maybe we simply write wrong data to the img when we store roads with points that are very close to each other?
If that is true, we might better try to find out what we have to write to the img instead of messing around with short arcs?
If only precision is the problem: Maybe we can Coord to store the lat/lon values with 30 bits precision?
Gerd
Hi Gerd,
interesting idea to increase the precision of coordinates. I sometimes thought about using "real" coordinates but using doubles instead of int seemed to be too much memory overhead. Increasing the precision to 30 bits seems to be a much better way.
The crucial point is: does the higher precision really help? In the end you also have to convert the high precision coordinates to the garmin precision. At this point I guess you will have the short arcs problem again? Of course the calculation of the bearings will be better. But this will not fix an img format problem (if that exist). So what about a systematic check the encodeCurve() method first? Would it be possible to create an map where all possible headings are encoded? In this case it might be possible to find out problematic values?!
WanMil
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/higher-precision-instead-of-short-arc-removal... Sent from the Mkgmap Development mailing list archive at Nabble.com.
@WanMil: Are you planning to merge back to trunk? If not, I should commit the coordPOI_v2.patch to trunk, and that would probably cause you trouble when merging. If found only small issues, e.g. the javadoc for resetHighwayCounts().
I don't think that I can merge the branch back to trunk right now. It's working great but first I want to improve the capabilities for style devs to set the access flags. Felix posted some notes and I think at least he is correct that the current handling requires too much more style implementation work to set all the different access flags. I can also not estimate how many style devs will bother when they realize that they *must* add their own handling for the access flags. Originally I also wanted to change the handling of the name tag. At the moment it is automatically combined with the mkgmap:display_name and mkgmap:ref tag. That's not very intuitive. WanMil
@WanMil: Are you planning to merge back to trunk? If not, I should commit the coordPOI_v2.patch to trunk, and that would probably cause you trouble when merging. If found only small issues, e.g. the javadoc for resetHighwayCounts().
I forgot to answer your second question: It will not cause trouble if you commit your changes both to trunk and the branch. I think I have commited most (if not all) of your patch.
participants (2)
-
GerdP -
WanMil