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 +0000, 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 <[email protected]> im Auftrag von
> Ticker Berkin
> <[email protected]>
> 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 +0000, 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 <[email protected]> im Auftrag von
> > Gerd Petermann
> > <[email protected]>
> > 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 <[email protected]> im Auftrag von
> > Ticker Berkin
> > <[email protected]>
> > 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 +0000, 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 LineClipperTest fails. I am not sure if only
> > > the test has to be
> > > changed (how) or if the code in LineClipper can be improved. I seem to
> > > remember that you
> > > suggested to use
> > > the code in ShapeSplitter instead.
> > >
> >
> > _______________________________________________
> > mkgmap-dev mailing list
> > [email protected]
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> > [email protected]
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> > [email protected]
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Index: src/uk/me/parabola/imgfmt/Utils.java
===================================================================
--- src/uk/me/parabola/imgfmt/Utils.java (revision 4912)
+++ src/uk/me/parabola/imgfmt/Utils.java (working copy)
@@ -116,15 +116,16 @@
* A map unit is an integer value that is 1/(2^24) degrees of latitude or
* longitude.
*
- * @param l The lat or long as decimal degrees.
+ * @param degrees The lat or long as decimal degrees.
* @return An integer value in map units.
*/
- public static int toMapUnit(double l) {
- final double DELTA = 360.0D / (1 << 24) / 2; //Correct rounding
- if (l > 0)
- return (int) ((l + DELTA) * (1 << 24)/360);
- else
- return (int) ((l - DELTA) * (1 << 24)/360);
+ public static int toMapUnit(double degrees) {
+ // do Round rather than Trunc: add a half and a lot extra so that the (int)op
+ // is always +ve to avoid neg trunc to zero and give uniform boundary behaviour
+ final double DELTA = 360.0D / (1 << 24) / 2 + 360.0D;
+ final double RESCALE = (1 << 24) / 360.0D;
+ final int UNDO360 = 1 << 24;
+ return (int)((degrees + DELTA) * RESCALE) - UNDO360;
}
/**
Index: src/uk/me/parabola/imgfmt/app/Coord.java
===================================================================
--- src/uk/me/parabola/imgfmt/app/Coord.java (revision 4912)
+++ src/uk/me/parabola/imgfmt/app/Coord.java (working copy)
@@ -669,9 +669,12 @@
* @return An integer value with {@code HIGH_PREC_BITS} bit precision.
*/
private static int toHighPrec(double degrees) {
- final double DELTA = 360.0D / FACTOR_HP / 2; // Correct rounding
- double v = (degrees > 0) ? degrees + DELTA : degrees - DELTA;
- return (int) (v * FACTOR_HP / 360);
+ // this is a bit like Utils.toMapUnit() except needs to be offset to give range -31..+32
+ // in each MapUnit in Coord() calc above; this is accomplished by not rounding
+ final double DELTA = 360.0D;
+ final double RESCALE = (1 << HIGH_PREC_BITS) / 360.0D;
+ final int UNDO360 = 1 << HIGH_PREC_BITS;
+ return (int)((degrees + DELTA) * RESCALE) - UNDO360;
}
/* Factor for conversion to radians using HIGH_PREC_BITS bits
_______________________________________________
mkgmap-dev mailing list
[email protected]
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
