Re: [mkgmap-dev] Gaps in surfaces
Hi Gerd
I've changed the way mapUnit and highPrec Coords are calculated slightly so
that the exact 1/2
unit boundary values are consistent between negative and positive. This gets
rid of my couple of
abnormalities with a -32 delta. The old method added or subtracted 1/2 to make
((int)double) do
rounding, which assigns the exact 1/2 to the larger abs value.
toHighPrec(), as in yesterdays change, keeps its bounds consistent with the
mapUnit it is
splitting up but is now coded in a similar way to toMapUnit.
I think rounding to get MapUnits is a mistake but changing it now could have
drastic
consequences, it should have been floorToNegInfinity, giving the nice cyclic
scale -128..+127 <<
24. As it is, we get -128..+128 << 24.
Equator & Grenwhich Meridian behave well, but I've always had doubts about
behaviour around 128
Hope this makes sense - patch attached
Sorry, haven't thought about the actual problem with the gaps yet.
Ticker
On Thu, 2023-10-05 at 07:30 +, Gerd Petermann wrote:
> Hi Ticker,
>
> reg. the change in toHighPrec() : I must confess that I never doubted why
> positive values
> should be rounded differently to negative values.
> This is also done in Utils.toMapUnit() and I just adapted that code. If you
> still want to
> change that I think Math.rint() would get you closer to the original
> implementation.
> Question is if or why this difference in rounding is/was needed. There should
> be visible
> effects near equator and at Greenwhich or at 180°.
>
> Anyhow, I don't think this is the solution for the gap problem which is
> caused by further
> conversions from highprec int to double and back.
> An alternative solution for that problem would be the attached patch which
> makes use of the
> coord pool.
> No idea which one has more effects on performance.
>
> Gerd
>
>
>
>
>
> Von: mkgmap-dev im Auftrag von
> Ticker Berkin
>
> Gesendet: Mittwoch, 4. Oktober 2023 15:57
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Gaps in surfaces
>
> Hi Gerd
>
> I've been thinking about how to stop the small ranges of decimal degrees from
> generating
> MapUnit/delta=+32 and MapUnit+1/delta=-32.
>
> Without changing the MapUnit value, but truncating the highPrec calc, eg, in
> Coord.java
>
> private static int toHighPrec(double degrees) {
> final double CVT_HP = ((double)(1 << HIGH_PREC_BITS)) / 360;
> return (int)Math.floor(degrees * CVT_HP);
> }
>
> this problem almost goes away, with deltas between -31 .. +32 except for 2
> instances of delta
> of
> -32 I get while building the Britain-and-ireland.osm.pbf. I need to work out
> why these are
> happening.
>
> Although it is unnatural to have this range rather than -32..+31, it doesn't
> matter. It
> probably
> could be fixed by using Math.ceil instead or reversing where the delta goes.
> getAlternativePositions() will generated delta values approx -48..+48.
>
> I don't get failures from LineClipperTest with this change.
> I do get failures from GmapsuppTest, SimpleRouteTest & SortTest, but I think
> these are not
> significant to this issue.
>
> As far as the gap between areas is concerned, I haven't looked at this yet
> but I'll see if my
> change has similar effects to your patch to Coord.
>
> Ticker
>
> On Wed, 2023-10-04 at 08:16 +, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > I've uploaded the test case: https://files.mkgmap.org.uk/detail/564
> > I had to modify the data a bit since the default style doesn't render
> > natural=heath
> >
> > Gerd
> >
> >
> > Von: mkgmap-dev im Auftrag von
> > Gerd Petermann
> >
> > Gesendet: Montag, 2. Oktober 2023 16:58
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] Gaps in surfaces
> >
> > Hi Ticker,
> >
> > the word overflow might be confusing. The problem is that we want to use
> > only 6 bits for the
> > delta, but we store values from -32 .. 32.
> > The special case with Michael example is that one coord with such an
> > extreme delta is used
> > (after converting to double) in Area.subtract() and the returned coord is
> > converted back but
> > get's the other extreme. In the end, only the 24 bit value is written to
> > the map, and that
> > causes the gap.
> >
> > Gerd
> >
> >
> > Von: mkgmap-dev im Auftrag von
> > Ticker Berkin
> >
> > Gesendet: Montag, 2. Oktober 2023 15:55
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] Gaps in surfaces
> >
> > Hi Gerd
> >
> > Considering no_hp-overflow_alpha.patch:
> >
> > It seems wrong to change a 24bit coordinate. Utils.toMapUnit() is well
> > defined to do the
> > expected rounding with the conversion.
> >
> > The actual deltas are local to Coord.java and, apart from their use by
> > getAlternativePositions,
> > are just used to get back to the highPrec coord value.
> >
> > The
Re: [mkgmap-dev] Gaps in surfaces
Hi Ticker,
reg. the change in toHighPrec() : I must confess that I never doubted why
positive values should be rounded differently to negative values.
This is also done in Utils.toMapUnit() and I just adapted that code. If you
still want to change that I think Math.rint() would get you closer to the
original implementation.
Question is if or why this difference in rounding is/was needed. There should
be visible effects near equator and at Greenwhich or at 180°.
Anyhow, I don't think this is the solution for the gap problem which is caused
by further conversions from highprec int to double and back.
An alternative solution for that problem would be the attached patch which
makes use of the coord pool.
No idea which one has more effects on performance.
Gerd
Von: mkgmap-dev im Auftrag von Ticker
Berkin
Gesendet: Mittwoch, 4. Oktober 2023 15:57
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] Gaps in surfaces
Hi Gerd
I've been thinking about how to stop the small ranges of decimal degrees from
generating
MapUnit/delta=+32 and MapUnit+1/delta=-32.
Without changing the MapUnit value, but truncating the highPrec calc, eg, in
Coord.java
private static int toHighPrec(double degrees) {
final double CVT_HP = ((double)(1 << HIGH_PREC_BITS)) / 360;
return (int)Math.floor(degrees * CVT_HP);
}
this problem almost goes away, with deltas between -31 .. +32 except for 2
instances of delta of
-32 I get while building the Britain-and-ireland.osm.pbf. I need to work out
why these are
happening.
Although it is unnatural to have this range rather than -32..+31, it doesn't
matter. It probably
could be fixed by using Math.ceil instead or reversing where the delta goes.
getAlternativePositions() will generated delta values approx -48..+48.
I don't get failures from LineClipperTest with this change.
I do get failures from GmapsuppTest, SimpleRouteTest & SortTest, but I think
these are not
significant to this issue.
As far as the gap between areas is concerned, I haven't looked at this yet but
I'll see if my
change has similar effects to your patch to Coord.
Ticker
On Wed, 2023-10-04 at 08:16 +, Gerd Petermann wrote:
> Hi Ticker,
>
> I've uploaded the test case: https://files.mkgmap.org.uk/detail/564
> I had to modify the data a bit since the default style doesn't render
> natural=heath
>
> Gerd
>
>
> Von: mkgmap-dev im Auftrag von Gerd
> Petermann
>
> Gesendet: Montag, 2. Oktober 2023 16:58
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Gaps in surfaces
>
> Hi Ticker,
>
> the word overflow might be confusing. The problem is that we want to use only
> 6 bits for the
> delta, but we store values from -32 .. 32.
> The special case with Michael example is that one coord with such an extreme
> delta is used
> (after converting to double) in Area.subtract() and the returned coord is
> converted back but
> get's the other extreme. In the end, only the 24 bit value is written to the
> map, and that
> causes the gap.
>
> Gerd
>
>
> Von: mkgmap-dev im Auftrag von
> Ticker Berkin
>
> Gesendet: Montag, 2. Oktober 2023 15:55
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Gaps in surfaces
>
> Hi Gerd
>
> Considering no_hp-overflow_alpha.patch:
>
> It seems wrong to change a 24bit coordinate. Utils.toMapUnit() is well
> defined to do the
> expected rounding with the conversion.
>
> The actual deltas are local to Coord.java and, apart from their use by
> getAlternativePositions,
> are just used to get back to the highPrec coord value.
>
> The deltas are stored as byte, so the value of +32 causes no arithmetic
> problems generally.
>
> getAlternativePositions(), however, should handle any complications with the
> +32, but it looks
> like it mostly does, bumping up or down the 24bit coord if the abs(deltas)
> are > 16. It it
> really possible that modLxxDelta can overflow a byte here?
>
> Haven't looked at LineClipperTest yet.
>
> Ticker
>
> On Fri, 2023-09-29 at 06:57 +, Gerd Petermann wrote:
> > Hi all,
> >
> > I've found out that this problem is caused by a flaw in the "high
> > precision" code. Under
> > special conditions, two points with almost identical coordinates are
> > internally represented
> > with very different values. There is a possible overflow in the delta
> > values, the value +32
> > should not occur as it cannot be represented with 6 bits, but the
> > calculations produce this
> > value.
> > I think I have an ugly fix for this but the resulting map still shows
> > (smaller) gaps and a
> > unit test needs corrections, so there is more to do.
> > Attached is a patch that checks for this overflow. Work in progress and
> > maybe causes trouble
> > in other areas, e.g. in South America where we have negative lat/lon values.
> >
> > @Ticker: The unit test für
