logo separator

[mkgmap-dev] RE Commit r3801: merge split-shape branch

From Gerd Petermann GPetermann_muenchen at hotmail.com on Fri Feb 24 10:54:38 GMT 2017

Hi Ticker,

okay, here are my findings so far:
1) We assume that the double values read from OSM or polist (*.mp) format are precise
2) The code in the Coord class tries to reduce rounding errors. It calculates both the 24 values AND the high prec values
from the given doubles. An alternative would be to calculate only the high prec values from the doubles and then
calculate the 24 bit values by shifting, but that would in fact mean that the value is rounded two times. In some edge cases
you will get different 24 values doing this. The delta values are stored in the Coord instance and for 30 bits precision
they are -32 <= delta < 32. 
The picture grid1 shows some OSM elements and the Garmin Grid (24 bit resolution):
and what the "normal" rounding does (note the zig-zagging rails)

3) The method Coord.getAlternativePositions() called by WrongAngleFixer introduces some additional problems:
It creates Coord instances where the delta values can be up to 63 (-63 <= delta < 63). This sounds much, but it only happens for OSM nodes
which are far from any Garmin grid point. Imagine that an OSM node lies exactly in the center of four Garmin grid points.
All four would have the same rounding error, but the distance between them can be ~2.3 m.
Which of the four Garmin points should be returned by the Coord.getDisplayedCoord() method?
For a single POI like a natural=peak it doesn't really matter, but for a node which is part of a roundabout or a railway=rail 
you want to get the point which "looks" better. A human knows by experience that rails are not zig-zagging, so 
the goal of the WrongAngleFixer is find the Garmin point which causes the smallest errors in the angles.
This is not only done for points which lie exactly in the center of Garmin grid points, but for all which are not close to one such point.
The WrongAngleFixer uses a iterative try-error approach to find those nodes which should be "moved", and it needs to know the
"original" position. I found no performant way to implement that with hashmaps, so I decided to code what we have now.
The improved result looks like this:

Later in the data flow the routines for the road network also need to know the real positions when they calculate the bearing values.

In short: I found no better solution, it works quite well but one has to think twice if he needs the Garmin position or the high prec (OSM) position.

Worth noting is that the WrongAngleFixer is called for lines and shapes, but at different stages. 
For lines (and roads), it is called  before MapLine instances are created. For shapes, it is called by the ShapeMergeFilter
which is called after all the sub division splitting happened. 
That means In the current code (r3820), the ShapeSplitter doesn't have to care about "moved" points in shapes.

Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <GPetermann_muenchen at hotmail.com>
Gesendet: Dienstag, 21. Februar 2017 20:01:06
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] RE Commit r3801: merge split-shape branch

Hi Ticker,

okay, I'll try to find out (again) why I decided to do the move only in low-prec. I know that I was not happy with that, but I forgot the reason. I think one was that the WrongAngleFixer started to move points too far. Anyway, I should fix this first.

I started to go for 32 bits because some algos which I coded for JOSM use this res. It seemed easier to change mkgmap to
also use 32 bits, but I am no longer sure about that.

Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
Gesendet: Dienstag, 21. Februar 2017 18:44:35
An: mkgmap-dev at lists.mkgmap.org.uk
Betreff: Re: [mkgmap-dev] RE Commit r3801: merge split-shape branch


According to my calcs, full 32 bit integers give a resolution of about
10mm at the equator. Why do you need better than existing high-res (30
bits - ~40mm)? Maybe go to 31 to save the +-180 degree problem.

Not to have the resolution as a powerOfTwo of the garmin map unit would
require a lot of changes throughout the code and a run-time cost.

Manipulating high-res deltas such that the rounded values diverges from
the the std lat/long value seems very wrong (is this what it does, or
does it simply change one but not the other). Maybe wrong-angle stuff
should be looked at to see if there is a better way. This is an area
I've never been near.

Would be great if Area/bounds and Coord used the same (high-prec) units
and there was no ambiguity about contains().


mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk

More information about the mkgmap-dev mailing list