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...

 

[blue_raver22]

for your question. I can understand your desire for a faster method to fit the tightest rectangle to a set of 3-D points. While the method you are currently using is effective, there are alternative approaches that may be faster. One possible method is called the rotating calipers algorithm. This algorithm involves using a pair of parallel lines to completely enclose the set of points, and then rotating the lines to find the tightest fit. This method has been shown to be efficient and accurate in finding the minimum area enclosing rectangle for a set of points.

Another approach is to use the convex hull of the points. The convex hull is the smallest convex polygon that contains all the points in a set. By finding the convex hull of your 3-D points, you can then find the smallest rectangle that encloses the convex hull. This method has been shown to be efficient and can also handle more complex point distributions.

In terms of programming, there are also libraries and algorithms available that can help you efficiently find the tightest rectangle for your set of points. For example, the OpenCV library has a function called "minAreaRect" which can quickly find the minimum area enclosing rectangle for a set of points.

Overall, while your current method is effective, there are alternative approaches that may be faster and more efficient in finding the tightest rectangle for your set of 3-D points. I suggest exploring these options and considering the specific requirements and constraints of your project to determine the best approach for your needs.