[R-sig-Geo] Diameter of a polygon
baptiste.auguie at googlemail.com
Wed Apr 13 22:50:27 CEST 2011
On 14 April 2011 01:51, Barry Rowlingson <b.rowlingson at lancaster.ac.uk> wrote:
> On Wed, Apr 13, 2011 at 12:42 PM, Karl Ove Hufthammer <karl at huftis.org> wrote:
>> Is it possible to easily calculate the diameter of a (large) polygon,
>> i.e. the longest distance between two points of the polygon? For a
>> rectangle, this would be the length of a diagonal.
>> The two points need not be actual vertices of the polygons (or must they
>> necessarily be so?).
> For a convex polygon it must be vertices of the polygon
> [http://cgm.cs.mcgill.ca/~orm/diam.html] and for a non-convex polygon
> I can't see how it could be anything other than points on the convex
> hull [conjecture]. That web site gives an algorithm in pseudo code,
> but there's the dumb approach of doing:
> where xc and yc are the coords of your polygon.
>> I’m also interested in the shortest length. For a rectangle, this would be
>> the length of the shortest side.
> Sounds like the 'width' - although again here its for convex
> polygons, possibly the convex hull of a non-convex polygon can be
>> And perhaps also the longest line that can be placed inside the polygon.
>> Note that this may easily be shorter than the longest diameter, as the
>> corresponding diameter line may pass outside the polygon. (Though I guess
>> for the *shortest* line, it would be identical to the smallest diameter.)
> For non-convex polygons that sounds like a very hard problem, since
> you could have all sorts of little bays and inlets that would mess up
> your long line. This is definitely a case where the end points wouldnt
> need to be vertices of the polygon. The shortest line that can be
> placed inside a polygon is easy - it has length zero!
I guess by "shortest line" he meant "shortest chord", right?
> R-sig-Geo mailing list
> R-sig-Geo at r-project.org
More information about the R-sig-Geo