[R-sig-Geo] Diameter of a polygon
Barry Rowlingson
b.rowlingson at lancaster.ac.uk
Wed Apr 13 15:51:21 CEST 2011
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:
max(dist(cbind(xc,yc)))
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
used:
http://cgm.cs.mcgill.ca/~orm/width.html
> 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!
Barry
More information about the R-sig-Geo
mailing list