[mkgmap-dev] shape merger in high-prec-coord branch

Wed Jan 15 07:28:48 GMT 2014

Hi WanMil,

forgot to mention that my algo simply doesn't merge when the result is not plausible.
You can see that in the unit tests. The idea:
If the area of the merged polygon is not equaul to the sum of the 
areas of the original polygons there was an overlap and I don't know 
how to handle that.
One open problem is the presumption that OSM data doesn't contains
self intersecting polygons, because for those the routine that calculates
the area is not working.
Assume this simple case:
A     B

C     D

A polygon CABDC will work fine, the self intersecting polygon ABCDA
will not. I plan to add a test for that and split those polygons in the beginning.
Wikipedia says that the Bentley-Ottmann algo should work for this:
http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
I think that might also help in the MultiPolygonRelation code,
but I found no copyright free java implementation until now.

Gerd

> Date: Tue, 14 Jan 2014 13:17:13 -0800
> From: gpetermann_muenchen at hotmail.com
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] shape merger in high-prec-coord branch
> 
> Hi WanMil,
> 
> WanMil wrote
> > The description of the algorithm sounds quite easy. I like it!
> > Maybe it could also be used to improve cutting in the Multipolygon class?
> > How do you avoid that two shapes connected with two edges and that 
> > surround a hole are merged? I think many shapes cut by the 
> > MultipolygonRelation have this characteristic.
> 
> the trick is that the merge is done for one sub division. That means
> that I just have to make sure that the number of points < 250
> so that no further routine splits the shape.
> 
> It might be possible to move the merge higher up in the chain,
> for example after the clipping. In that case I have to make sure
> that I don't create shapes that PolygonSubdivSizeSplitterFilter would split.
> 
> I know that this is a bit risky, but maybe I can get rid of all 
> Java2DConverter methods that convert to double and back to int.
> 
> Gerd
> 
> 
> 
> --
> View this message in context: http://gis.19327.n5.nabble.com/shape-merger-in-high-prec-coord-branch-tp5793093p5793099.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20140115/2584472f/attachment-0001.html>