[mkgmap-dev] Multipolygon-Relation checks in mkgmap

Wed Feb 1 09:44:43 GMT 2017

Hi Ticker,

yes, you are probably right. My new algo produces a result similar to
the old one directly followed by ShapeMergeFilter.
I think most of the complex logic in MultiPolygonCutter is used to find
the best place for splitting. The target is probably to find cut lines which go through more than one inner
ring so that the number of splits is reduced. Other important targets are
- aspect ratio should be small
- added lines should be short

Maybe you find a way to implement that without using java area or maybe with fewer uses.

I have a cold and cannot concentrate well, so sorry for the noise.

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, 1. Februar 2017 10:24:43
An: mkgmap-dev at lists.mkgmap.org.uk
Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

I got lost in the logic of MultiPolygonRelation, but the impression I
got was it cut right through the outer polygon to expose the inner one,
which it could then combine into one of the bits of the outer if it
just touches the edge of the inner - just adding the points in the same
direction.

ShapeMergeFilter might partially rejoin the outer.

Ticker

On Wed, 2017-02-01 at 08:33 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> you are right that self-intersecting polygons are not allowed in OSM.
> On the other hand,
> the current code in MultiPolygonRelation is meant to produce self
> intersecting polygons
> as it connects the holes with the outer shapes. As far as I know the
> Garmin algos do not care
> about self intersection, so up to now I never cared about the
> direction of the ways when connecting
> them to the outer shape. I think that means that java area code also
> doesn't care.
> Anyhow, I think that problem is solved with the reversing.
>
> I am running further tests with r3781 rnow.
>
> 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, 31. Januar 2017 18:35:11
> An: mkgmap-dev at lists.mkgmap.org.uk
> Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap
>
> Hi Gerd
>
> ShapeSplitter only works on a single-path shape. Considering the act
> of
> splitting a shape with a single line, you are left with a list of
> lines
> that start and end on the divider. These lines don't cross each other
> unless the polygon was self-intersecting which is not allowed.
>
> Then, just considering one side of the divider, the complexities of
> how
> the other side contorted to define multiple holes in a shape, and
> shapes in a hole can all be ignored. Lines going one way relating to
> the dividing line define the outer edge of a shape, and if the shape
> has direct holes, they must go the other way.
>
> I think the above is true for any non-self-intersecting polygon.
>
> ShapeSplitter has to resort to using the sign of the area of a shape
> defined by one of these lines and the divider only when multiple
> lines
> start and end at the same point.
>
> It can handle a shape and hole going through a single dividing point,
> so can easily cope with dividing a polygon where there is a single
> cut
> to an inner hole. Without self-intersection, if the dominant
> direction
> of the polygon is, say, anti-clockwise, then the hole must be
> clockwise.
>
> Does this make sense?
>
> Ticker
>
> On Tue, 2017-01-31 at 15:41 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > thanks, will look again later.
> > I am working on a patch for the MultiPolygonCutter. It works
> > without
> > java.awt.geom.Area, the basic idea is to connect shapes
> > where they are close to each other. I've tried that in 2012, maybe
> > I
> > get it working now.
> > One problem that I've noticed:
> > The code in ShapeSplitter seems to consider some shapes as self
> > -intersecting when the connected inner ways are clockwise (or not
> > clockwise,
> > not sure which one causes trouble). I assume you coded this because
> > the shapes produced by java.awt.geom.Area are like that, outer
> > shape
> > is
> > one direction and inner shapes are in the other direction. I have
> > some problems with this behaviour, is it needed ?
> > For now I found a work around by reversing the ways so that they
> > are
> > ordered. Attached is a patch with what I coded so far, open
> > problems
> > are mp-rels at tile boundaries and performance. Be careful, the
> > code
> > contains lots of GPXCreator statements and other debug code.
> >
> > 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, 31. Januar 2017 16:26:41
> > An: mkgmap-dev at lists.mkgmap.org.uk
> > Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap
> >
> > Hi Gerd
> >
> > I've think I've finished making all the changes I want to do at the
> > moment - It seems to work nicely. Sometime can you merge the branch
> > back if you are happy with it.
> >
> > Thanks
> > Ticker
> >
> >
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev