[Date Index] [Thread Index] [Author Index]

Re: Fit rectangle to set of points

• To: mathgroup at smc.vnet.net
• Subject: [mg69349] Re: Fit rectangle to set of points
• From: "David W.Cantrell" <DWCantrell at sigmaxi.net>
• Date: Thu, 7 Sep 2006 23:58:45 -0400 (EDT)
• References: <edom0n$hu2$1@smc.vnet.net>

"buttgereit at biomediclab.de" <buttgereit at biomediclab.de> wrote:
> Dear Group,
>
> I have a set of 2D points given for which I would like to find the
> smallest rectangle circumscribing all the points.

Smallest perimeter or smallest area or ...? I will assume you want smallest
area.

> Doing this with a circle instead of a rectangle was easy --- for the
> rectangle I don't see the trick.
>
> Any hints?

Of course you need consider only the convex hull of your set of points.
A function for finding the convex hull is in the standard package
DiscreteMath`ComputationalGeometry` .

Have you looked at the literature on this topic? A Google web search for
"smallest enclosing rectangle" led me to, among other references,

<http://ceng.usc.edu/~prasanna/papers/jang-97.pdf>.

Please see their section 3.2 .

David