I have an arbitrary number of points which are all located on a plane in 3D space. I need to find the four corner points of the rectangle which tightly encloses all points. how can i do that?

thank you!

"Tightly encloses" is ill-defined. If you mean the rectangle with minimal area, this is called the minimal enclosing rectangle problem and can be solved in linear time. See http://cgm.cs.mcgill.ca/~orm/maer.html

For other definitions of "tightly encloses" it may be significantly easier or significantly harder.

You need to view those points in an axis-aligned space.

Multiply each point's transform by the inverse of the plane's transform.

You should use a change of coordinates. Take your normal vector, find two unit vectors that are perpendicular to it and to each other and use that as your base. In these new coordinates, your plane is z = constant and you can deal with the x and y coordinates as if you were in 2D.

How exaclty would I do that? I store my planes as normal plus distance to origin.

Your 'normal' describes a rotation, and the 'distance to origin' describes a position. With these two elements you can build a transformation matrix that represents your plane's space.
If you want to view your points in an axis-aligned manner, multiply their XYZ coordinates by the inverse of this matrix. This can be viewed as aligning the plane with your world's origin - you are removing any transformations from this plane, and bringing the points with it. Any distance these points had towards the plane's origin, now they will have the same towards the world's origin.

After you've multiplied them all with the plane's inverse matrix and stored their new position results, find out the enclosing rectangle with the algorithm of your choice - run it on these stored positions you have. This should give you the 4 points for the enclosing rectangle. Multiply each of these 4 points' XYZ coordinates by the plane's matrix to bring them back into the plane's space, which would be akin to having the rectangle get aligned with that arbitrary plane, whichever rotation it might have. This is your transformed rectangle.

For me the most difficult part here would be to extract a rotation from the plane's normal vector - I don't have any resources at hand where this is shown easily. I use an API with utilitary functions for this.

[quote name='Vexator' timestamp='1321566918' post='4885127']
I have an arbitrary number of points which are all located on a plane in 3D space. I need to find the four corner points of the rectangle which tightly encloses all points. how can i do that?

thank you!

"Tightly encloses" is ill-defined. If you mean the rectangle with minimal area, this is called the minimal enclosing rectangle problem and can be solved in linear time. See http://cgm.cs.mcgill.ca/~orm/maer.html

For other definitions of "tightly encloses" it may be significantly easier or significantly harder.
[/quote]

Are you sure it can be solved in linear time? The link you posted only seems to solve it in linear time for convex polygons. I can't really think of quick way to prove that it's not possible in linear time for an arbitary set of points, but I have a suspicion that its not possible.

Is this kind of approach would work (linear time) ?
Pseudo code follows.
Basically, you try to expand the rectangle, starting with zero dimentions.



struct rectangle
{
vector2d upperLeft ;
vector2d lowerRight ;
} ;
rectangle boundRec;
boundRec.upperLeft = boundRec.lowerRight = points[0] ;

for (int i = 0 ; i < points.size() ; i++)
{
if(points.X > boundRec.lowerRight.X) boundRec.lowerRight.X = points.X ;
if(points.Y > boundRec.lowerRight.Y) boundRec.lowerRight.Y = points.Y ;
if(points.X > boundRec.upperLeft .X) boundRec.upperLeft .X = points.X ;
if(points.Y > boundRec.upperLeft .Y) boundRec.upperLeft .Y = points.Y ;
}

Is this kind of approach would work (linear time) ?
Pseudo code follows.
Basically, you try to expand the rectangle, starting with zero dimentions.



struct rectangle
{
vector2d upperLeft ;
vector2d lowerRight ;
} ;
rectangle boundRec;
boundRec.upperLeft = boundRec.lowerRight = points[0] ;

for (int i = 0 ; i < points.size() ; i++)
{
if(points.X > boundRec.lowerRight.X) boundRec.lowerRight.X = points.X ;
if(points.Y > boundRec.lowerRight.Y) boundRec.lowerRight.Y = points.Y ;
if(points.X > boundRec.upperLeft .X) boundRec.upperLeft .X = points.X ;
if(points.Y > boundRec.upperLeft .Y) boundRec.upperLeft .Y = points.Y ;
}

That always gives axis aligned rectangle. The minimal one will often not be axis aligned.