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

Sun Jan 4 21:08:51 GMT 2015

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
>