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