I'm sure anyone who has gotten as far as opening this thread will be familiar with least squares (and other variants) regression - for fitting a straight line to a series of (x,y) points.

The procedure can be easily generalised to a higher dimension, e.g. fitting a plane to a series of (x,y,z) co-ordinates.

However in each case we're dealing with a shape which is inifinite.

How might be go about fitting a rectangular 'patch' to a series of 2D points, or a cube to a series of 3D points?

Taking the cube example, I can think of two (loosely conceived) approaches:

a) The cube can be defined by 9 paramaters - the x,y,z offset, the length of each side and the 3 orienting angles. Pick some values of these. Associate each point in your series with the nearest face in the cube. Calculate the sum of the distances from their associated faces. Minimize this 'error' by using an optimization routine on the 9 'input' parameters

b) Assuming that we can define a 'rough surface' by connecting the appropriate points in our series using triangular patches (which is true in my application), succesively eliminate individual vertices in our shape until the AIC (Aikake) is mimized

anyone got any thoughts or suggestions on how to proceed - either using the above approaches or any other?

The first thing that comes into my head is to do Principal Components (=find the eigensystem of the variance-covariance matrix), and replace the resulting error ellipsoid with the rectangle/parallelipiped/etc that contains it. The error ellipsoid has various desirable properties as far as goodness of fit, and the rectangle is guaranteed to have an area 4/pi times the area of the ellipse.

I dont completely understand the question

Say in an easy case, you have 3 points: {(0,0),(0,1),(1,0)}. And your given a fixed rectangle? Or your trying to fit any new rectangle to these points?

The point is, do you prefer the rectangle where (0,1) and (1,0) are adjacent corners and (0,0) is on the midpoint of the opposite side?

I can't figure out what you are trying to determine.. like in the line/2d points case, we're trying to minimize a sum of squares...

Hi DoubleIce

I'm trying to fit a rectangle to the given points.

The context is that I have a surface (or more accurately a series of surfaces) measured at discrete points - these measurements including errors.

For example, imagine I had a perfect cube. The measurements I take, due to measurement error, noise etc, would not correspond exactly to this shape - but I'd like to be able to 'recover' the 'true shape'

It isn't as simple as fitting a line to a set of points though, because in that case all points are associated with that line, so you just minimise the sum of squared distances. In this case, points are associated with different planes (in the 3D case) or edges (in the 2D case)

I think you have the answer in (a) -- you need to minimize something. There's going to be a problem in that a unique minimizer might not exist.

It's also going to be ugly because there won't necessarily be a unique "closet point" between some measured value and your cube.