Re: [mkgmap-dev] Gaps in surfaces
Hi Gerd Sorry - bit hasty in my reply I need to look at the other places that use DELTA_SHIFT and check their arithmetic/rounding etc is consistent with the corrected highPrecCoord and uniform in rounding behaviour. Ticker On Fri, 2023-10-06 at 16:15 +0100, Ticker Berkin wrote: > Hi Gerd > > My change to toMapUnit should be almost undetectable. Imagining mapUnits [x] > as degrees over > the > real range -2.5 .. +2.5, the original implementation resulted in: > > -2.5 < [-2] <= -1.5 < [-1] <= -0.5 < [0] < -0.5 <= [1] < +1.5 <= [2] < > +2.5 > > I've changed it to give: > > -2.5 <= [-2] < -1.5 <- [-1] < -0.5 <= [0] < -0.5 <= [1] < +1.5 <= [2] < > +2.5 > > The change to highPrecCoord is so that 64 highPrecCoords are exactly within > the appropriate > mapUnit, with deltas of -31..+32 according to the existing delta calculations. > > Ticker > > On Fri, 2023-10-06 at 14:34 +, Gerd Petermann wrote: > > Hi Ticker, > > > > your patch rounds the problematic point to a different position, the same > > that is assigned > > to > > the new Coord instance that is derived from the cutOutInnerPolygons() method > > which involves singularAreaToPoints() and thus another place where rounding > > happens: > > int latHp = (int)Math.round(res[1] * > > (1< > int lonHp = (int)Math.round(res[0] * > > (1< > > > I think we have to check all nodes which are part of an inner and change > > position because of > > your different rounding method, right? I wouldn't be surprised to find > > cases where a gap > > occurs > > with (just) your patch. I'll try to find an example... > > If I can't we may just use your patch, although it's much harder to > > understand compared to > > the > > original code. > > > > Gerd > > ___ > 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 Gerd My change to toMapUnit should be almost undetectable. Imagining mapUnits [x] as degrees over the real range -2.5 .. +2.5, the original implementation resulted in: -2.5 < [-2] <= -1.5 < [-1] <= -0.5 < [0] < -0.5 <= [1] < +1.5 <= [2] < +2.5 I've changed it to give: -2.5 <= [-2] < -1.5 <- [-1] < -0.5 <= [0] < -0.5 <= [1] < +1.5 <= [2] < +2.5 The change to highPrecCoord is so that 64 highPrecCoords are exactly within the appropriate mapUnit, with deltas of -31..+32 according to the existing delta calculations. Ticker On Fri, 2023-10-06 at 14:34 +, Gerd Petermann wrote: > Hi Ticker, > > your patch rounds the problematic point to a different position, the same > that is assigned to > the new Coord instance that is derived from the cutOutInnerPolygons() method > which involves singularAreaToPoints() and thus another place where rounding > happens: > int latHp = (int)Math.round(res[1] * > (1< int lonHp = (int)Math.round(res[0] * > (1< > I think we have to check all nodes which are part of an inner and change > position because of > your different rounding method, right? I wouldn't be surprised to find cases > where a gap > occurs > with (just) your patch. I'll try to find an example... > If I can't we may just use your patch, although it's much harder to > understand compared to the > original code. > > Gerd ___ 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 Ticker, your patch rounds the problematic point to a different position, the same that is assigned to the new Coord instance that is derived from the cutOutInnerPolygons() method which involves singularAreaToPoints() and thus another place where rounding happens: int latHp = (int)Math.round(res[1] * (1< im Auftrag von Ticker Berkin Gesendet: Freitag, 6. Oktober 2023 16:19 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Gaps in surfaces Hi Gerd I've now looked at your example (mp-gap2.osm). With my toMapUnit/toHighPrec patch the problem almost disappears. I don't see any significant difference when I also apply your mp-cut-coord- pool.patch. I can't see a way of fixing these gaps/overlaps without disabling a lot of filter point-removal, maybe by setting Coord.preserved() and ensuring added points for polygon cutting are on both the inner and outer polygon, which I thought they were, with the algorithm cutting through the complete structure and then bits being merged later if possible. Ticker On Thu, 2023-10-05 at 16:37 +0100, Ticker Berkin wrote: > 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 > > > > > >
Re: [mkgmap-dev] Gaps in surfaces
Hi Gerd I've now looked at your example (mp-gap2.osm). With my toMapUnit/toHighPrec patch the problem almost disappears. I don't see any significant difference when I also apply your mp-cut-coord- pool.patch. I can't see a way of fixing these gaps/overlaps without disabling a lot of filter point-removal, maybe by setting Coord.preserved() and ensuring added points for polygon cutting are on both the inner and outer polygon, which I thought they were, with the algorithm cutting through the complete structure and then bits being merged later if possible. Ticker On Thu, 2023-10-05 at 16:37 +0100, Ticker Berkin wrote: > 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