Jump to content
  • Advertisement
Sign in to follow this  
Vexator

find rectangle around points on plane

This topic is 2578 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites
thanks for the link! I'm having trouble computing the extreme points, though. If it was in 2D I'd know how to do it but on an arbitrary plane in 3D, I'm not sure huh.gif

Share this post


Link to post
Share on other sites
You need to view those points in an axis-aligned space.

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

Share this post


Link to post
Share on other sites
[color=#1C2837][size=2]Multiply each point's transform by the inverse of the plane's transform. [/quote]


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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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 ;
}

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!