[mkgmap-dev] Multipolygon-Relation checks in mkgmap

Wed Feb 1 08:33:00 GMT 2017

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