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@hotmail.com To: mkgmap-dev@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-tp5793... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev