Fitting the 'tightest' rectangle to a set of three dimensional points

[Cbas]

I have a group of 8 3-D points which all sit on an arbitrary plane
(The points were generated by projecting the corners of a axis aligned cube, box, onto the plane)
I wish to group all the points in a rectangle with the smallest surface area - so a tight fit rectangle.

What I am doing at the moment is:
1. transforming the plane (and thus all the points) to be parallel with the x-,y-plane (The z-axis points to the zenith). Thus each point is now described by only an (x,y) value (as they all have the same z value)
2. Fitting a rectangle now is trivial as I just find the smallest and largest (x,y) values and these make the lower left and upper right corners of my rectangle respectively
3. Transform the corners of the rectangle back to the plane.

Is there faster way of doing this (I am programming this so I favour speed)

Thank you very much

 

[oli4]

Hi Cbas
That would depend a lot on the previous steps you had for the projection on the plane, how you did it and the actual necessity of doing it
For instance, you could 'rotate your scene' from the beginning so that you are facing the plane and you don't have to project your points anymore, just take the min (x,y) and max (x,y) right from your cube and ignore the z value
If you must do this projection for whichever purpose, then how is your plane given ? how do you make the projection ? can't you simply get within those steps the coordinates of the projected points in the plane's (one of the plane's) coordinates, you will have a set of x' and y' and do the same thing and won't have to transform back and forth.

Cheers...

 

[Cbas]

Thanks Oli,

This is what I am given:
The (x,y,z) coordinates of each corner of the box and the normal n of the plane...

I think you might be right, somewhere in the projection steps is the key but I coan't quite crack it. This is how I project:

The equation of the plane:
(p-a)°n=0 (1)
(° is dot product)
Using the furthest corner of the box for a (offset slightly)

Equation of a 'ray'
p=o+tn (2)
Where o is the corner of each box

Solving for t : (2) into (1)

t = (a-o)n/(d°n) (3)

Substitude t back into to (2) to get p

p is the (x,y,z) point on the plane.
I do that for each corner...
Does that help?

 

[oli4]

Hi Cbas
Yes it helps, now I know that the projection is along the normal of the plane and apparently it does not matter where the plane actually is (any // plane would do if I understood correctly your 'picking the furthest corner of the box')
You could pick any corner then, it wouldn't change anything and you don't have to know which one is furthest. the first corner in the list is OK
you take it as being your 'origin' in this plane, and you pick 2 orthogonal normalized vectors in this plane so as to be a basis.
Then, no ray needed, your first point is already known, it has coordinates (0,0) in the plane's basis, and for all the others, you just dot product those basis vectors with your other corners, (that will give them their coordinates in this plane, and you keep track of min(x',y') and max(x',y') as you go along, getting you directly the rectangle you were looking for)
I'm not sure about your plane not being specified by more than its normal, so if you have a given point, well you use it instead of using the first corner of the cube

Cheers...