[R-sig-Geo] Diameter of a polygon

baptiste auguie 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:
>
> 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!

I guess by "shortest line" he meant "shortest chord", right?

baptiste

>
> Barry
>
> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at r-project.org
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo
>



More information about the R-sig-Geo mailing list