[mkgmap-dev] small issue with Way.getCofG()

Tue Jan 6 13:30:39 GMT 2015

Hi,

I coded the described algo, it contained a small error, but seems to work,
but it is much slower than the simple existing algo, esp.
in those cases were the simple algo works fine,
as it requires tons of rather complex distance calculations
for each polygon.
I will look for some optimization, but I think the improvement
is too small for now.

Gerd

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