<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 12pt;
font-family:Calibri
}
--></style></head>
<body class='hmmessage'><div dir='ltr'>Hi WanMil,<br><br>forgot to mention that my algo simply doesn't merge when the result is not plausible.<br>You can see that in the unit tests. The idea:<br>If the area of the merged polygon is not equaul to the sum of the <br>areas of the original polygons there was an overlap and I don't know <br>how to handle that.<br>One open problem is the presumption that OSM data doesn't contains<br>self intersecting polygons, because for those the routine that calculates<br>the area is not working.<br>Assume this simple case:<br>A B<br><br>C D<br><br>A polygon CABDC will work fine, the self intersecting polygon ABCDA<br>will not. I plan to add a test for that and split those polygons in the beginning.<br>Wikipedia says that the Bentley-Ottmann algo should work for this:<br>http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm<br>I think that might also help in the MultiPolygonRelation code,<br>but I found no copyright free java implementation until now.<br><br>Gerd<br><br><div>> Date: Tue, 14 Jan 2014 13:17:13 -0800<br>> From: gpetermann_muenchen@hotmail.com<br>> To: mkgmap-dev@lists.mkgmap.org.uk<br>> Subject: Re: [mkgmap-dev] shape merger in high-prec-coord branch<br>> <br>> Hi WanMil,<br>> <br>> WanMil wrote<br>> > The description of the algorithm sounds quite easy. I like it!<br>> > Maybe it could also be used to improve cutting in the Multipolygon class?<br>> > How do you avoid that two shapes connected with two edges and that <br>> > surround a hole are merged? I think many shapes cut by the <br>> > MultipolygonRelation have this characteristic.<br>> <br>> the trick is that the merge is done for one sub division. That means<br>> that I just have to make sure that the number of points < 250<br>> so that no further routine splits the shape.<br>> <br>> It might be possible to move the merge higher up in the chain,<br>> for example after the clipping. In that case I have to make sure<br>> that I don't create shapes that PolygonSubdivSizeSplitterFilter would split.<br>> <br>> I know that this is a bit risky, but maybe I can get rid of all <br>> Java2DConverter methods that convert to double and back to int.<br>> <br>> Gerd<br>> <br>> <br>> <br>> --<br>> View this message in context: http://gis.19327.n5.nabble.com/shape-merger-in-high-prec-coord-branch-tp5793093p5793099.html<br>> Sent from the Mkgmap Development mailing list archive at Nabble.com.<br>> _______________________________________________<br>> mkgmap-dev mailing list<br>> mkgmap-dev@lists.mkgmap.org.uk<br>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<br></div> </div></body>
</html>