[mkgmap-dev] low-res-opt branch: error message from ShapeSplitter for self-intersecting multipolygon

Thu Jun 10 10:38:44 BST 2021

Hi Gerd

The logic of ShapeSplitter is based on polygons not self-intersecting
and this is what makes it fast.

OSM polygons are not self-intersecting unless they are in error.

MultiPolygon processing should be stopped from generate them; there is
no need. Once they occur and have to be handled later in the processing
it will add complications to splitting and probably to merging.

ShapeSplitter doesn't make any attempt to detect self-intersection and
it won't notice many occurrences of it; it depending on where the cut
-line is and if signs of areas make sense. Often the result will be
"rubbish-out" for self-intersecting input. This means it is unreliable
to catch problems when it does detect them and use some alternate
algorithm.

Although Garmin might render simple figure-of-8 in what seems like a
sensible way, what happens when there is [multiple] overlap etc. Some
polygon rendering algorithms alternate shape/not-shape for each
additional overlap. Do all other programs that display Garmin .img do
the same thing? I'd rather avoid this question and never cause self
-intersection.

Ticker

On Tue, 2021-06-08 at 07:43 +0000, Gerd Petermann wrote:
> Hi Ticker,
> 
> my understanding is that Garmin software has no problems with this
> kind of self-intersection.
> In this particular case the problem could be solved in method
> MultipolygonRelation.joinWays(), as 4 ways are connected at the same
> point, but self-intersecting shapes are also possible as simple ways.
>   While they are wrong for OSM they should be allowed for MapShape
> since Garmin allows them, too.
> 
> A possible way to fix those shapes is something like this:
>                         Path2D.Double path =
> Java2DConverter.createPath2D(polygonPoints);
>                         path.setWindingRule(Path2D.WIND_EVEN_ODD);
>                         List<List<Coord>> shapes =
> Java2DConverter.areaToShapes(new java.awt.geom.Area(path));
> So, maybe ShapeSplitter could do this with the input shape in case of
> error and try again with shapes?
> 
> Gerd
> 
> ________________________________________
> Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> von Ticker Berkin <rwb-mkgmap at jagIT.co.uk>
> Gesendet: Dienstag, 8. Juni 2021 08:54
> An: mkgmap-dev at lists.mkgmap.org.uk
> Betreff: Re: [mkgmap-dev] low-res-opt branch: error message from
> ShapeSplitter for self-intersecting multipolygon
> 
> Hi Gerd
> 
> The shape is a figure-of-8 so shapesSplitter needs to give some
> error.
> 
> If this isn't an original OSM shape, it points to some problem with
> earlier processing, probably shape-merging. Although it might render
> (could be device dependent), further processing (eg overview merging)
> could come to grief.
> 
> Ticker
> 
> On 07/06/2021 10:24, Gerd Petermann wrote:
> > Hi Ticker,
> > 
> > okay, no problem, I'll work on the faster-mp branch in the mean
> > time
> > Maybe I'll merge it first into the low-res-opt branch.
> > 
> > Gerd
> > 
> > ________________________________________
> > Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> > von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> > Gesendet: Montag, 7. Juni 2021 11:23
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] low-res-opt branch: error message from
> > ShapeSplitter for self-intersecting multipolygon
> > 
> > Hi Gerd
> > 
> > The shape I'm getting in my build has a major problem with a twist
> > between the 2 parts. I'm having trouble reconciling it with the OSM
> > map. I've attached the original shape trace.
> > 
> > I agree that some of the messages do need tweaking, but, in this
> > cases
> > there is a significant problem.
> > 
> > I'll consider the types of messages etc in the new version I'm
> > working
> > on.
> > 
> > I'm away for a few days and won't be able to do much remotely.
> > 
> > Ticker
> > 
> > On Mon, 2021-06-07 at 07:22 +0000, Gerd Petermann wrote:
> > > Hi Ticker,
> > > 
> > > please check 
> > > https://files.mkgmap.org.uk/download/512/63240024.o5m
> > > with (unpatched) r4756 and these options --generate
> > > -sea=multipolygon,floodblocker --preserve-element-order --order
> > > -by
> > > -decreasing-area
> > > --allow-reverse-merge
> > > 
> > > Produces an error message
> > > SCHWERWIEGEND (ShapeSplitter):
> > > e:\osm_out_work\norway\20210511_095323\63240024.o5m: Vertical
> > > split
> > > 36691968 failed on shape at
> > > http://www.openstreetmap.org/?mlat=65.979056&mlon=12.308790&zoom=
> > > 17 P
> > > ossibly a self-intersecting polygon
> > > for this invalid multipolygon :
> > > https://www.openstreetmap.org/relation/5294624
> > > 
> > > The result doesn't look wrong, so I think there should either be
> > > no
> > > error message or we need code to remove those self-intersections
> > > or
> > > ignore invalid MP like that?
> > > 
> > > 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