Introduction:
In this tutorial we will show how to detect the intersection between a line and a rectangle. OpenGL programmers know that it is easy to detect rectangle/line intersection when the rectangle edges are parallel to x or y axes. In our tutorial the rectangle will not be parallel to x or y instead it will be rotated by an angle. Our method will be done by detecting the intersection of the line with all the edges of the rectangle. If the line intersects with at least one edge so we know that it is intersected with the rectangle. A very important application is to detect the cursor collision with the rotating rectangle. Some times it is needed to know whether the cursor is rolling over the rectangle or not. It is also needed when trying to detect the cursor collision with the text – text can be labels rotated with a small angle. The idea for detecting a cursor passed over the text is to get the line between the cursor and the center of the bounding box ( box around the text) and check if the line intersects with the bounding box or not. If so this means the cursor is outside the rectangle, otherwise, means the cursor is inside the bounding box and there is no intersection.
First, we will show how to setup our OpenGL screen. Then we will show how to get the bounding box of a text. Finally we present the line/rectangle intersection algorithm.
1- OpenGL screen setup:
For this algorithm to work properly, we need to setup the coordinate system. Since the cursor position is given with respect to the upper-left corner of the screen (the origin 0,0) we need to do the Ortho Projection the same way as in the following code segment:
gluOrtho2D(0.0,screen_width,screen_height,0.0); So the origin of the OpenGL screen will be also at the upper left corner of the screen, see Figure 1
Figure 1: OpenGL screen setup
The “virtual” bounding box
We are going to calculate x,y coordinates of the 4 corners of the text, see Figure2. Given the rotation angle “the text angle”, the start point (point a in Figure2), the width, and the height of the text we are going to calculate b,c,d points of the bounding box.
Figure 2: the bounding box represents by its four corners
Notice: We can’t use the CRect or similar structure, since it uses only two points, i.e. Point d and Point b in Figure2; it doesn’t deal with the rotation. We are going to use our special structure for RECT, we will call it ROT_RECT. It has the following structure
struct ROT_RECT{ POINT Pa,Pb,Pc,Pd;};Pa,Pb,Pc, and Pd are the corner points a,b,c and d shown in Figure2.
Figure 3: calculating the bounding box with taking the rotation angle into account
Now we are going to implement a function that will take rot (rotation angle of the text Figure 3), a(x,y) (the coordinate of the text), the wid ( the width of the text) and hgt (the height of the text), the function will return ROT_RECT, it is the rectangle which is drawn around the text ( the bounding box of the text) with its four corner points. The function code is:
ROT_RECT buildRectangle(GLfloat rot,GLfloat x,GLfloat y,GLfloat wid,GLfloat hgt){ //This function calculates the bounding box for the text //rot is the rotation angle of the text //x,y is the position of the text //wid, hgt is width/height of the text ROT_RECT temp_rect; const float piover180 = 0.0174532925f; GLfloat bx,by,cx,cy,dx,dy; bx=x+wid*cos(rot*piover180);by=y+wid*sin(rot*piover180); //rot is angular in OpenGL cx=x+wid*cos(rot*piover180)-hgt*sin(rot*piover180);cy=y+hgt*cos(rot*piover180)+wid*sin(rot*piover180); dx=x-hgt*sin(rot*piover180);dy=y+hgt*cos(rot*piover180); // Implement the rectangle temp_rect.Pa.x=x;temp_rect.Pa.y=y; temp_rect.Pb.x=bx;temp_rect.Pb.y=by; temp_rect.Pc.x=cx;temp_rect.Pc.y=cy; temp_rect.Pd.x=dx;temp_rect.Pd.y=dy; return temp_rect;}3- The cursor/text collision detection
In section 2, we obtained the four corner points of the text. To detect the cursor/text collision, we are going to use the “virtual” rectangle or a bounding box of the text. Then the collision of the cursor with that rectangle will be detected by connecting a “virtual” line from the cursor to the center point of the rectangle. If this line goes through any of the four edges of the rectangle this means the cursor is not on the text. If the line didn’t cross the edges of the rectangle this means the cursor inside the rectangle (on the text), see Figure 4
Figure4: the intersection of the line from the cursor with the bounding box of the text
In Figure 4, the cursor is outside the rectangle (not over the text), to calculate this by programming, we need to detect the “cross” between the line Cur-Cent.(the green line) and ALL the rectangle edges, i.e. lines a-b, b-c, c-d, and d-a. If we found an intersection between the line and one of the rectangle edges this means the cursor is outside the rectangle. If there is no intersection, this means the cursor is over the text.
The calculation of the cursor/text collision will be calculated in the following steps. First we will show how to detect Line-Line intersection, then we will check the intersection of the line from the text center to the cursor with all the edges of the rectangle to show whether the cursor is over the text or not.
3.1 Line-Line Intersection
The line-line intersection can be done by detecting a common point on the two lines as shown in Figure 5.
Figure 5: The intersection of two lines.
The intersection point (Red point in Figure 4) coordinates will be calculated. We are going to build a function that will return that point whenever there is an intersection otherwise it will return NULL, the implementation is as follow:
POINT* intersection(POINT p1, POINT p2, POINT p3, POINT p4) { // Given two lines, the first line is p1-p2 //the second line is p3-p4 float x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x; float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y; float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); // If d is zero, there is no intersection if (d == 0) return NULL; // Get the x and y float pre = (x1*y2 - y1*x2), post = (x3*y4 - y3*x4); float x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d; float y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d; // Check if the x and y coordinates are within both lines if ( x < min(x1, x2) || x > max(x1, x2) || x < min(x3, x4) || x > max(x3, x4) ) return NULL; if ( y < min(y1, y2) || y > max(y1, y2) || y < min(y3, y4) || y > max(y3, y4) ) return NULL; sprintf(string,"CrossX: %d ",x); drawText(string,10,60); sprintf(string,"CrossY: %d ",y); drawText(string,10,50); // Return the point of intersection POINT* ret= new POINT; ret->x = x; ret->y = y; return ret;}3.2 Rectangle-Cursor Collision
The above function (intersection) will be used to calculate the intersection point of the following objects:
1- The line connecting the cursor position with the center of the bounding box, the green line in Figure4.
2- The bounding box, (the box around the text).
A function called ( isCursorInside) will be implemented. The function return true (in case of the cursor inside the rectangle) and false (in case of the cursor is far away). The function code is:
bool isCursorInside(ROT_RECT rect,POINT cursor_pos){ //calculate the center point of the rectangle //in is the intersection point for the four corners POINT center=intersectionPoint(rect.Pa,rect.Pc,rect.Pb,rect.Pd); //check intersection of line from cursor to the center //of the rectangle with a-b edge if(intersection(cursor_pos,center,rect.Pa,rect.Pb) != NULL)return true; //with b-c edge if(intersection(cursor_pos,center,rect.Pb,rect.Pc) != NULL)return true; //with c-d edge if(intersection(cursor_pos,center,rect.Pc,rect.Pd) != NULL)return true; //with d-a if(intersection(cursor_pos,center,rect.Pd,rect.Pa) != NULL)return true; return false;}The intersectionPoint is a function calculates the intersection point (the center of the bounding box) its implementation is as follow:
POINT intersectionPoint(POINT p1, POINT p2, POINT p3, POINT p4) { // Given two lines, the first line is p1-p2 //the second line is p3-p4 float x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x; float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y; float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); // Get the x and y float pre = (x1*y2 - y1*x2), post = (x3*y4 - y3*x4); float x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d; float y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d; // Return the point of intersection POINT ret; ret.x = x; ret.y = y; return ret;}isCursorInside is the most important function here since it detects whether the cursor is inside the bounding box or not.
This way we are able to detect a line/rectangle intersection and we studied an application in which this detection is extremely needed. i.e. the detection of the collision of the cursor with the a rotated text.
OpenGL Line/Rectangle Intersection Sample Code:
You can Download the Sample code for the above OpenGL Article and check for Instructions on how to run the OpenGL Program.