[mkgmap-dev] Problems with sea in overview map

Thu May 20 10:25:09 BST 2021

Hi Gerd

I'm getting worried by rounding-to-resolution and how often it creates
self-intersection.

When doing the shapeSplitter.splitShape, we found that, unless
operating with high-precision points (ie there were problems at 24bit
precision), it could fail because of self-intersection.

The polygon points limit filters got around this by tricky
backtracking. This option isn't available when the overview map is
being generated as the problem points have been frozen at very low res.

Also thinking that shapeMerge might need to operate at highPrecision.

I'm just trying do work out if the different levels have their own copy
of shapes pre-filtering and how this effects what shapeMerge does as
makeMapAreas steps through the levels.

Ticker

On Thu, 2021-05-20 at 09:07 +0000, Gerd Petermann wrote:
> Hi Ticker,
> 
> I've attached a test case that shows how the order is important.
> Depending on the order of shapes to be merged the resulting shape
> sometimes is self-intersecting, sometimes it isn't.
> I've not yet understood what the trigger is.
> 
> Gerd
> 
> 
> ________________________________________
> Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> von Gerd Petermann <gpetermann_muenchen at hotmail.com>
> Gesendet: Mittwoch, 19. Mai 2021 18:14
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Problems with sea in overview map
> 
> Hi Ticker,
> 
> yes, I think ShapeMerger can always merge. There seems to be no need
> to look at the number of points. Maybe 24 is an exception.
> 
> Sorting has an effect, but not always to the better.
> 
> The merger is already used with rounded coord when the shapes for the
> overview map are merged.
> 
> Attached is a patch that shows what I am playing with. Will continue
> tomorrow...
> 
> Gerd
> 
> 
> ________________________________________
> Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> Gesendet: Mittwoch, 19. Mai 2021 17:41
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Problems with sea in overview map
> 
> Hi Gerd
> 
> I still haven't deciphered the complicated bits of ShapeMergeFilter.
> 
> Could it do the testing of mergeable candidates with rounded-to
> -resolution points, then, if merging, convert all the points.
> 
> Regardless, the limit checks against MAX_POINT_IN_ELEMENT could use
> PredictFilterPoints(). It isn't a major problem if this limit is
> exceeded because filtering might take it below again and, if it
> doesn't, PolygonSplitter will deal with it.
> 
> Regarding ordering, maybe if merge succeeds for some potential
> shapes,
> they should all be done.
> 
> Intersecting polygons from rounding of concave shapes with a long
> diagonal is slightly insoluble. Maybe something like WrongAngleFixer
> is
> going to be needed. Multipolygon cuts that are vertical or horizontal
> might be less of a problem.
> 
> I'm considering the effect of different orders of filters, such that
> if
> a small hole becomes a point and cuts to it, after merging, become a
> series of spikes going into the shape, removeObsoletePoints removes
> it.
> 
> Ticker
> 
> On Wed, 2021-05-19 at 14:12 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> > 
> > I think ShapeMergeFilter could be part of the problem. It sometimes
> > finds strange ways to merge shapes, esp. when many small parts can
> > be
> > merged. Maybe this can be improved by sorting so that it merges
> > from
> > top to bottom.
> > 
> > Gerd
> > 
> > ________________________________________
> > Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> > von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> > Gesendet: Mittwoch, 19. Mai 2021 14:14
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] Problems with sea in overview map
> > 
> > Hi Gerd
> > 
> > I've just been experimenting and looking at shapes and rounding-to
> > -low
> > -resolution can easily cause self-intersections.
> > 
> > It isn't just a problem with sea, or even with multipolygon hole
> > cutting. GPSMapEdit reports over 1000 in my test area. This number
> > reduces only slightly when I disable DP for polygons. Generally
> > these
> > are not noticeable - a little bit of wood missing when zoomed out
> > isn't
> > obvious, but same is not true of sea.
> > 
> > Ticker
> > 
> > On Wed, 2021-05-19 at 11:43 +0000, Gerd Petermann wrote:
> > > Hi Ticker,
> > > 
> > > no need to guess, I use GpxCreator in various places to visualize
> > > input and output of filters. I load the gpx files into JOSM and
> > > maybe
> > > convert to Data layer to understand what happens, e.g. where the
> > > start /end point is.
> > > Reg. self-intersection:
> > > Think of a merged sea shape with several islands in it. The
> > > rounding
> > > may result in only three or four different nodes, visitied in a
> > > more
> > > or less random order while the correct shape would be a triangle
> > > or
> > > rectangle.
> > > Not sure if this is only a problem with sea, probably not.
> > > 
> > > Feel free to try other orders of the filters, or maybe different
> > > algos to set the preserved flag. There is definitely room for
> > > improvements. I've played with this very often and sometimes one
> > > area
> > > is improved and another is worsened.
> > > 
> > > Gerd
> > 
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev