Geometry Boost List: Re: [geometry] how to find the furthest point pair (= diameter) of a polygon?

Subject: Re: [geometry] how to find the furthest point pair (= diameter) of a polygon?
From: Mateusz Loskot (mateusz_at_[hidden])
Date: 2013-08-14 12:05:05

On 14 August 2013 15:59, Barend Gehrels <barend_at_[hidden]> wrote:
> On 14-8-2013 15:01, Tanaka Simon wrote:
>
> Hello,
>
> I have a polygon and like to find the pair of points defining the largest
> distance (also known as diameter problem).
>
> the question is also formulated here:
> http://stackoverflow.com/questions/6524350/algorithm-to-find-points-that-are-furthest-apart-better-than-on2
>
> is there a boost::geometry implementation? something like
> bg::diameter(bg::model::polygon<>)
>
>
> Exactly this function with this name and functionality is indeed planned.
> Alas it is not yet available.

Barend,

By the way, could you share a bit more about what algorithm is planned?
A brute force approach, like in PostGIS [1], or any of the known algorithms [2],
or anything else?

[1] ST_MinimumBoundingCircle
http://svn.osgeo.org/postgis/trunk/postgis/postgis.sql.in
[2] http://en.wikipedia.org/wiki/Smallest-circle_problem

Best regards,
-- 
Mateusz  Loskot, http://mateusz.loskot.net
"Participation in this whole process is a form of torture" ~~ Szalony,
wspinanie.pl