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

Wed Jan 7 09:29:51 GMT 2015

HI Gerd, the method I've used won't work if the polygon is thinner than the
resolution of the bitmap. I hadn't considered that it might be used on
rivers; my main testing has been on car parks, which although they may be
irregularly shaped are not normally very long and very thin (I handle river
names from the underlying lines). There are two possible problems that could
occur - if a polygon is thin enough that it renders in the bitmap as a line
that is nowhere wider than 2 pixels the POI could be placed just outside the
polygon. I haven't checked what fillPolygon does if the points have no
volume and form a line. If this renders nothing, then the algo will just
return the centre point, which could be nowhere near the polygon. A simple
solution to the first problem would be to examine the
biggestSquaredDistanceToBlack figure before returning the coordinate and if
the value is 1, repeat the operation on a small area around the point to get
a better accuracy. I'll look into that. For the second problem I'll add an
error message, so we can determine if it actually occurs
(biggestSquaredDistanceToBlack is 0). I've also thought that having drawn
the bitmap, it might be more efficient to then copy its contents out into an
array so that finding the distances from pixels inside the polygon to those
outside become simple array lookups instead of graphics function calls. I'll
look into that as well.

Cheers,
Mike

From: Gerd Petermann [mailto:gpetermann_muenchen at hotmail.com] 
Sent: 07 January 2015 06:55
To: mkgmap-dev at lists.mkgmap.org.uk
Subject: Re: [mkgmap-dev] small issue with Way.getCofG()

Hi Mike,

on my PC the performance of your algo is quite good. 
Attached is a patch that contains your patch as well as my quick
implementation
of the algo described here:
http://arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf

The patch tests only performance, it computes the center with the 3
different algos,
I've commented the part that prints times and GPX data for debug purposes.

I noticed that the results between both algos are very different, I did not
yet try to find out which one is better, but mine is much slower on my PC.
I also noticed that your algo doesn't always calculate a point in the
polygon,
see e.g.   way 178708143.

If you like, please try to find a better compromise, I like to fix a problem
in
splitter first.
I also did not yet look at the effect on the house number code, as there are
many
more small open problems, but I think it should be easy to sort that out.

Gerd

> Date: Tue, 6 Jan 2015 13:23:57 -0700
> From: gpetermann_muenchen at hotmail.com
<mailto:gpetermann_muenchen at hotmail.com> 
> To: mkgmap-dev at lists.mkgmap.org.uk <mailto:mkgmap-dev at lists.mkgmap.org.uk>

> Subject: Re: [mkgmap-dev] small issue with Way.getCofG()
> 
> Hi Mike,
> 
> I like the idea, but it seems to be slow.
> Is it possible that your algo suffers when no fast graphics card is
> available?
> On my netbook the performance is very poor, did not yet
> try on the PC, but that also has no high speed graphics.
> 
> Gerd
> 
> 
> GerdP wrote
> > Hi Mike,
> > 
> > 50% sounds better than my algo, but still quite a lot. I'll have a
closer
> > look at your
> > algo later.
> > Please note that your change has a side effect on the house number
> > generator.
> > Up to now this doesn't contain a filter for generated POI, so each
polygon
> > with a house number is processed twice, once because of the POI, once
> > because the Generator uses Way.getCofG(). If both have different
positions
> > this might have a negative impact.
> > 
> > Gerd
> > 
> > 
> > From: 
> 
> > mike at .co <mailto:mike at .co> 
> 
> > To: 
> 
> > mkgmap-dev at .org <mailto:mkgmap-dev at .org> 
> 
> > Date: Tue, 6 Jan 2015 14:56:30 +0000
> > Subject: Re: [mkgmap-dev] small issue with Way.getCofG()
> > 
> > I have a working solution for ensuring that the created point is placed
> > within the polygon when using --add-pois-to-areas, based on drawing the
> > polygon on to a small monochrome bitmap and then looking for the point
> > that
> > is furthest from the surrounding area. I used a 9x9 bitmap for polygons
> > having a small number of points and 15x15 for longer polygons. There is
> > however a performance penalty. My standard map takes about 1 hour 20
> > minutes; using this algorithm the time increases by about 50% to about 2
> > hours. I am not currently able to commit changes to SVN (perhaps someone
> > can
> > help out with that) but I have attached the code changes. I suggest that
> > due
> > to the performance penalty, if we adopt this, then the
--add-pois-to-areas
> > option be extended to be --add-pois-to-areas[=centre|optimised] or
> > something
> > similar, with the default being centre and functioning as now and the
> > optimised option invoking the new code. Please try out the suggested
> > change.
> > Note I don't expect this to work properly where a polygon is formed from
a
> > multiploygon relation, but the code could quite easily be adapted for
this
> > circumstance.
> > 
> > 
> > Regards,
> > Mike
> > 
> > _______________________________________________
> > mkgmap-dev mailing list
> 
> > mkgmap-dev at .org <mailto:mkgmap-dev at .org> 
> 
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev 
> > _______________________________________________
> > mkgmap-dev mailing list
> 
> > mkgmap-dev at .org <mailto: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-tp5828821p582924
7.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk <mailto: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/20150107/e29a3de1/attachment-0001.html>