On Wed, Apr 13, 2011 at 12:42 PM, Karl Ove Hufthammer <[email protected]> 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 _______________________________________________ R-sig-Geo mailing list [email protected] https://stat.ethz.ch/mailman/listinfo/r-sig-geo
