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

Sun Jan 4 13:39:24 GMT 2015

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.