bounding rectangle

I'm not very good with matrices either, so this is the technique I use to rotate a rectangle in my 2D game clicky. You just rotate the centre point around the origin and then translate back into position.

As for the minimum bounding rectangle, this is much easier :) Start by initialising two points min and max to the first vertex, then loop through the other vertices doing a simple greater than/less than test for each one against the min and max points, pseudocode:

// initialisepoint min = verts[0];point max = verts[0];// loop through pointsfor (int i=1;i<4;i++){  // mins  if (verts.x < min.x)    min.x = verts.x;  if (verts.y < min.y)    min.y = verts.y;  // maxes  if (verts.x > max.x)    max.x = verts.x;  if (verts.y > max.y)    max.y = verts.y;}// minimum rectangle = min to max

If you were wanting this in 3D then just add in a min/max test for the z co-ordinate.

I'm sure there's a better, neater and faster way of doing this but this works well for me :)

Hope that helps.

Thanks for the reply, but it doesn't quite solve my problem because I don't have the vertices of the rotated rectangle. I guess I could simplify my question to:

Whats a good way to find the rotated vertices? I only need to do it in 2D.

[Edited by - toxy on December 21, 2004 4:35:52 PM]

Actually the solution to your question is already there, I just didn't explain it very well :blush:

Let's start with a rectangle which is axis-aligned, i.e. not rotated. Now this rectangle has four points describing it: 0 (top-left), 1 (bottom-left), 2 (bottom-right) and 3 (top-right). The centre point of this rectangle can be found by taking the mid-point of the low and high x values and the low and high of the y values. To rotate the object about the origin just rotate each point using the formula from the link I gave you:

x' = cos(theta)*x - sin(theta)*y y' = sin(theta)*x + cos(theta)*ywhere theta is the angle by which to rotate the point.

Now say you wish to rotate the rectangle around its centre point, i.e. make it 'spin'. The first step is to translate the rectangles' points so they lie are around the origin, to do this just subtract the centre points' x and y from each of the four points describing the rectangle. Now you can rotate the rectangle around the origin. The final step is to add the centre point's x and y to each of the points, thereby translating them back into position but rotated.

Incidentally the function I gave you to find the minimum bounding rectangle can be used to find the centre point of this rotated rectangle, and indeed the old rectangle, to do this just get the mid point between the max and min points.

I really should exlpain things better but I'm full of bloody cold and I have a deadline approaching fast (tommorow, eek!). Anyway I hope this helped you ;)

Ok now I see:)

thanks a lot for your help. Take it easy.

toxy, eSCHEn pretty much nailed this down (quite well I might add) while I was off writting this up, about all I can offer in addition are some examples, and they haven't been compiled yet so they're not tested.

So if you're up for some more of the same, here's some thoughts:


Since there's three values for each vertex, it's easier to handle if we make a data struct that better suits our particular needs:

//global datatypedef struct{               float x;               float y;               float z;                }VERT;

In our program, we might reserve memory for four vertices (in the case of a rectangle):

//global data for tutorial purposesVERT v[4];

Now that we have some kind of storage, we plug-in our values:

Let's say we want a 5x3 box...

MakeBox(&v,5.0f,3.0f);  //first make the box                        //Now your 4 vertices are in v[];Render(&v);             //after you initialize, start render loop.//on any appropriate keypress, change the rotation angle//or translate the box:Rotate2D(&v, 45.0f);   //rotate 45 degreesMove2D(&v,1,10.0f);    //move up 10 unitsMove2D(&v,2,10.0f);    //move down 10 unitsMove2D(&v,3,10.0f);    //move right 10 unitsMove2D(&v,4,10.0f);    //move left 10 unitsRotate2D(&v, -45.0f);  //rotate back 45 degrees//...and so on...

Here's some routines that might show what's going on:
(absolutely *not* tested so you may need to 'tune' them)

//an example routine to initialize rectangle vertices//pass it address of your vertex array, width and height of boxMakeBox(VERT *v[], float WIDTH, float HEIGHT){//upper leftv[0]->x= -(WIDTH/2.0f);  //neg xv[0]->y=  (HEIGHT/2.0f); //pos yv[0]->z=   0.0f//upper rightv[1]->x= (WIDTH/2.0f);  //pos xv[1]->y= (HEIGHT/2.0f); //pos yv[1]->z=  0.0f//lower rightv[2]->x=  (WIDTH/2.0f);  //pos xv[2]->y= -(HEIGHT/2.0f); //neg yv[2]->z=  0.0f//lower leftv[3]->x= -(WIDTH/2.0f);  //neg xv[3]->y= -(HEIGHT/2.0f); //neg yv[3]->z=  0.0freturn 0;}

OK, so the values for each vertex are stored/initialized, now we can manipulate them.

//so move up, down, right, or left with this://(a rudimentary 2D TRANSLATE routine)//address of vertex array, direction(1,2,3,4), amount to move/////////////////////////////////////////////int Move2D(VERT *v[], int direction, float amount){int i, num, UP=1,DOWN=2,RIGHT=3,LEFT=4;num=(sizeof(v))/(sizeof(v[0]));for(i=0;i<num,i++){    switch(direction){          case UP:               v->y+=amount;          break;          case DOWN:               v->y-=amount;          break;          case RIGHT:               v->x+=amount;          break;          case LEFT:               v->x-=amount;          break;          default:          break;  }//switch}//forreturn 0;}//Move//rotate around a center with this://(a rudimentary 2D ROTATE routine)//address of vertex array, angle to rotate in degrees/////////////////////////////////////////////int Rotate2D(VERT *v[],  float angle){int i, num;num  =(sizeof(v))/(sizeof(v[0]));angle=deg2rad(angle);  //change degrees to radiansfor(i=0;i<num,i++){    v->x=v->x*cos(angle) - v->y*sin(angle);    v->y=v->y*cos(angle) + v->x*sin(angle);               }//forreturn 0;}//Rotate//You need these support routines too:///////////////////////////////////////////float deg2rad(float d){return (d*PI/180.0f);}float rad2deg(float r){return (r*180.0f/PI);}

Just put values in your vertices and render, that's pretty much it.

As for bounding rectangles, loop through your vertices (since now you know where to find them) and look for the smallest and largest x and y 'extents'.

The smallest-X and the largest-Y will be the upper-left corner of the box (as above), the largest-X and largest-Y will be the upper-left corner, the largest-X and smallest-Y will be the lower-right corner and the sallest-X and smallest-Y will be the lower-left corner.

That's the tightest box your rotated box will fit in.

So now you save the new vertices in a new VERT array and draw the bounding box...

Another (and faster, I guess) way to find the bounding rectangle:

Say I have sinTheta and cosTheta (Theta being the angle with which the rectangle is rotated)

double s = (sinTheta > 0) ? sinTheta : -sinTheta;
double c = (cosTheta > 0) ? cosTheta : -cosTheta;

newWidth = oldWidth * c + oldHeight * s;
newHeight = oldWidth * s + oldHeight * c;

That's it :)

Very cool harshdeep! I like it!