Re: [mkgmap-dev] Gaps in surfaces
Hi Ticker, no problem, I think this is a very old error ;) I think the remaining gaps (at res 24) are produced by the MultipolygonCutter. It sometimes cuts the outer and produces new points and these new points are not added to the inner rings, only to the outer. I have to find out if this can be fixed by avoiding these cuts or by modifying the inner rings. Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Freitag, 29. September 2023 11:03 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Gaps in surfaces Hi I was thinking that gaps like this could often happen when adjacent polygons share the points along the common boundary, but, during the various point-removal optimisations, esp. Douglas Peucker, different points along this boundary are chosen to represent the 2 polygons. Regarding LineClipperTest, I don't have the facilities to look at this until next week. 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 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. > > > Von: mkgmap-dev im Auftrag von Gerd > Petermann > > Gesendet: Dienstag, 26. September 2023 19:58 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] Gaps in surfaces > > Hi Michael, > > okay, I can reproduce the problem. I assume it is caused by the code which > subtracts the inner > area from the multipolygon area. > No idea if this can be fixed easily. > > Gerd > > > Von: mkgmap-dev im Auftrag von > Forstner Michael > > Gesendet: Dienstag, 26. September 2023 19:44 > An: 'Development list for mkgmap' > Betreff: Re: [mkgmap-dev] Gaps in surfaces > > Hello Gerd, > > here is the area: https://www.openstreetmap.org/#map=19/48.57117/13.96920 I > understand that it is necessary to make rounding. If a point of two surfaces > is equal in OSM, the point should also be equal in Garmin. > > Thank you! > > Best regards, > Michael > > > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Gaps in surfaces
Hi I was thinking that gaps like this could often happen when adjacent polygons share the points along the common boundary, but, during the various point-removal optimisations, esp. Douglas Peucker, different points along this boundary are chosen to represent the 2 polygons. Regarding LineClipperTest, I don't have the facilities to look at this until next week. 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 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. > > > Von: mkgmap-dev im Auftrag von Gerd > Petermann > > Gesendet: Dienstag, 26. September 2023 19:58 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] Gaps in surfaces > > Hi Michael, > > okay, I can reproduce the problem. I assume it is caused by the code which > subtracts the inner > area from the multipolygon area. > No idea if this can be fixed easily. > > Gerd > > > Von: mkgmap-dev im Auftrag von > Forstner Michael > > Gesendet: Dienstag, 26. September 2023 19:44 > An: 'Development list for mkgmap' > Betreff: Re: [mkgmap-dev] Gaps in surfaces > > Hello Gerd, > > here is the area: https://www.openstreetmap.org/#map=19/48.57117/13.96920 I > understand that it is necessary to make rounding. If a point of two surfaces > is equal in OSM, the point should also be equal in Garmin. > > Thank you! > > Best regards, > Michael > > > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Gaps in surfaces
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.
Von: mkgmap-dev im Auftrag von Gerd
Petermann
Gesendet: Dienstag, 26. September 2023 19:58
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] Gaps in surfaces
Hi Michael,
okay, I can reproduce the problem. I assume it is caused by the code which
subtracts the inner area from the multipolygon area.
No idea if this can be fixed easily.
Gerd
Von: mkgmap-dev im Auftrag von
Forstner Michael
Gesendet: Dienstag, 26. September 2023 19:44
An: 'Development list for mkgmap'
Betreff: Re: [mkgmap-dev] Gaps in surfaces
Hello Gerd,
here is the area: https://www.openstreetmap.org/#map=19/48.57117/13.96920 I
understand that it is necessary to make rounding. If a point of two surfaces
is equal in OSM, the point should also be equal in Garmin.
Thank you!
Best regards,
Michael
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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)
@@ -56,6 +56,7 @@
private static final int HIGH_PREC_BITS = 30;
public static final int DELTA_SHIFT = HIGH_PREC_BITS - 24;
private static final int MAX_DELTA = 1 << (DELTA_SHIFT - 2); // max
delta abs value that is considered okay
+ private static final int HIGH_DELTA = 1 << (DELTA_SHIFT - 1); //
positive delta that doesn't fit into 6 bits
private static final long FACTOR_HP = 1L << HIGH_PREC_BITS;
private static final int HIGH_PREC_UNUSED_BITS = Integer.SIZE -
HIGH_PREC_BITS;
@@ -83,24 +84,39 @@
}
/**
-* Construct from regular latitude and longitude.
+* Construct from regular latitude and longitude given in degrees.
* @param latitude The latitude in degrees.
* @param longitude The longitude in degrees.
*/
public Coord(double latitude, double longitude) {
- this.latitude = Utils.toMapUnit(latitude);
- this.longitude = Utils.toMapUnit(longitude);
+ int lat24 = Utils.toMapUnit(latitude);
+ int lon24 = Utils.toMapUnit(longitude);
int latHighPrec = toHighPrec(latitude);
int lonHighPrec = toHighPrec(longitude);
- this.latDelta = (byte) ((this.latitude << DELTA_SHIFT) -
latHighPrec);
- this.lonDelta = (byte) ((this.longitude << DELTA_SHIFT) -
lonHighPrec);
-
+ byte dLat = (byte) ((lat24 << DELTA_SHIFT) - latHighPrec);
+ byte dLon = (byte) ((lon24 << DELTA_SHIFT) - lonHighPrec);
+
+ // correct possible overflow in delta value
+ if (dLat == HIGH_DELTA) {
+ dLat = -HIGH_DELTA;
+ lat24--;
+ }
+ if (dLon == HIGH_DELTA) {
+ dLon = -HIGH_DELTA;
+ lon24--;
+ }
+
+ this.latitude = lat24;
+ this.longitude = lon24;
+ this.latDelta = dLat;
+ this.lonDelta = dLon;
+
// verify math
assert (this.latitude << DELTA_SHIFT) - (int) latDelta ==
latHighPrec;
assert (this.longitude << DELTA_SHIFT) - (int) lonDelta ==
lonHighPrec;
}
- private Coord (int lat, int lon, byte latDelta, byte lonDelta){
+ private Coord(int lat, int lon, byte latDelta, byte lonDelta) {
this.latitude = lat;
this.longitude = lon;
this.latDelta = latDelta;
@@ -118,7 +134,19 @@
