<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,<br><br>I coded the described algo, it contained a small error, but seems to work,<br>but it is much slower than the simple existing algo, esp.<br>in those cases were the simple algo works fine,<br>as it requires tons of rather complex distance calculations<br>for each polygon.<br>I will look for some optimization, but I think the improvement<br>is too small for now.<br><br>Gerd<br><br><div>> Date: Sun, 4 Jan 2015 22:08:51 +0100<br>> From: wmgcnfg@web.de<br>> To: mkgmap-dev@lists.mkgmap.org.uk<br>> Subject: Re: [mkgmap-dev] small issue with Way.getCofG()<br>> <br>> Hi Gerd,<br>> <br>> yep, good catch. Seems to be a good solution for mkgmap!<br>> <br>> WanMil<br>> <br>> > Hi WanMil,<br>> ><br>> > I think the problem is similar to finding the "largest circle in a concave<br>> > polygon",<br>> > and we are not interested in the exact solution, any point close enough to<br>> > the center is<br>> > good. See e.g.<br>> > http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf<br>> > which contains an iterative algo.<br>> ><br>> > Gerd<br>> ><br>> ><br>> > WanMil wrote<br>> >> Hi Gerd,<br>> >><br>> >> a good algorithm to find a point for the --add-pois-to-areas option<br>> >> would be to use the straight skeleton algorithm<br>> >> (http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2011q3/012394.html). This<br>> >> might be used to find a point with maximum distance to the border of a<br>> >> polygon. Anyhow it seems to be a complex algorithm so maybe not the<br>> >> ideal solution for mkgmap.<br>> >><br>> >> WanMil<br>> >><br>> >>> Hi Steve,<br>> >>><br>> >>> Steve Ratcliffe wrote<br>> >>>> On 03/01/15 08:15, Gerd Petermann wrote:<br>> >>>>> @Steve:<br>> >>>>> The routine was initially created for the --check-roundabouts option.<br>> >>>>><br>> >>>>> Later it was also used for --add-pois-to-areas and the --housenumbers<br>> >>>>> option.<br>> >>>>> I got the impression that it might be better to calculate the center<br>> >>>>> of the way bbox for those two, I am not so sure about the roundabout<br>> >>>>> code.<br>> >>>>> What do you think?<br>> >>>><br>> >>>> Seems like the current method would tend to place the point near the<br>> >>>> most complex part of the boundary. This may not be bad, I would have<br>> >>>> to see lots of real examples to be sure.<br>> >>><br>> >>> Yes, correct. I compared these three algos:<br>> >>> 1) the existing<br>> >>> 2) my patched one<br>> >>> 3) center of bbox<br>> >>> For complex shapes (many points), 1) and 2) produce almost equal<br>> >>> results, and in fact the point was more often within the shape.<br>> >>> For simple polygons like small parks, buildings, etc. 1) is worst,<br>> >>> 2) is better and 3) is best.<br>> >>><br>> >>> My conclusion: the patch is a simple and good improvement,<br>> >>> for housenumber location calculation maybe it would be better to use<br>> >>> algo 3).<br>> >>><br>> >>><br>> >>> Steve Ratcliffe wrote<br>> >>>> Anyway there are no easy (or even any difficult!) methods that work in<br>> >>>> all cases, so I would just keep it as it is and perhaps should the<br>> >>>> calculated point be outside the box, move it to the closest point<br>> >>>> inside.<br>> >>><br>> >>> I already looked at the link provided by Andrzej.<br>> >>> If I got that right, we have two different problems regarding<br>> >>> the generated POI:<br>> >>> We calculate it once for the whole polygon, before clipping<br>> >>> it to the bbox of the tile, and it might be outside of the polygon<br>> >>> as well as outside of the bbox.<br>> >>><br>> >>> This brought me back to the non-rectangular tile problem and I stop<br>> >>> searching for a solution for the POI problem.<br>> >>><br>> >>> Reg. non-rectangular tiles: I fear we can't use any of the existing<br>> >>> algos in mkgmap to implement this, I'll report details in a different<br>> >>> post.<br>> >>><br>> >>> Gerd<br>> >>><br>> >>><br>> >>><br>> >>><br>> >>> --<br>> >>> View this message in context:<br>> >>> http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p5828952.html<br>> >>> Sent from the Mkgmap Development mailing list archive at Nabble.com.<br>> >>> _______________________________________________<br>> >>> mkgmap-dev mailing list<br>> >>><br>> ><br>> >> mkgmap-dev@.org<br>> ><br>> >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<br>> >>><br>> >><br>> >> _______________________________________________<br>> >> mkgmap-dev mailing list<br>> ><br>> >> mkgmap-dev@.org<br>> ><br>> >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<br>> ><br>> ><br>> ><br>> ><br>> ><br>> > --<br>> > View this message in context: http://gis.19327.n5.nabble.com/small-issue-with-Way-getCofG-tp5828821p5828986.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>> ><br>> <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>