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