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

Wed Jan 7 06:54:39 GMT 2015

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
> To: 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
> 
> > To: 
> 
> > 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
> 
> > 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-tp5828821p5829247.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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20150107/ac2e08a4/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pointInPolygon-v0.patch
Type: application/octet-stream
Size: 16292 bytes
Desc: not available
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20150107/ac2e08a4/attachment-0001.obj>