Public Group

# Collision detection with diagonal lines

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

## Recommended Posts

So I have a rectangle that begins in a standard upright position with two vertical lines and two horizontal lines. As the program progresses, the rectangle may rotate in either direction, thus changing the angle with respect to the origin of the aforementioned lines When the lines are horizontal and vertical to the axes, I can simply test collisions between the x and y boundaries of the box. This is not possible once it begins rotating, since the lines are no longer parallel to any of the axes. But I still need to detect when an object collides with one of these lines. I was thinking that I could find the equation of the line and then simply test all of the x and y coordinates along this line. I would make a for loop.
[source lang=c++]
for (int x = 0; x < length of line; x++)
{
y = mx + b;
//store the x and the cooresponding y that the above equation produces.
//Now I have all the points on the line
}
for every point on line
{
if (collision == true)
....do stuff


I suppose I could test every 5 coordinates or something like that to improve performance. The objects are big enough such that a collision will still be detected, and as long as the user cannot notice that the object is partially passing through the rectangle, I'm fine. Is this a decent approach? Thank you

##### Share on other sites
How are your objects represented? Circles? Rectangles? Points?

One trick you can do, is to keep track of the rectangle's rotation, then, when you want to see if a circle object or a point collides with the rectangle, you can apply a negative rotation to both the rectangle and object (circle/point) which should give you back vertical/horizontal lines for the rectangle that you can then test the object against.

##### Share on other sites
Quote:
 Original post by zoner7So I have a rectangle that begins in a standard upright position with two vertical lines and two horizontal lines. As the program progresses, the rectangle may rotate in either direction, thus changing the angle with respect to the origin of the aforementioned linesWhen the lines are horizontal and vertical to the axes, I can simply test collisions between the x and y boundaries of the box. This is not possible once it begins rotating, since the lines are no longer parallel to any of the axes.But I still need to detect when an object collides with one of these lines. I was thinking that I could find the equation of the line and then simply test all of the x and y coordinates along this line. I would make a for loop.*** Source Snippet Removed *** I suppose I could test every 5 coordinates or something like that to improve performance. The objects are big enough such that a collision will still be detected, and as long as the user cannot notice that the object is partially passing through the rectangle, I'm fine.Is this a decent approach?Thank you
Stepping along the lines in discrete intervals is not how this is normally done; it's messy and inaccurate, and may not even be faster than alternate approaches.

Also, the line form y = mx + b is problematic in that it cannot represent all lines uniformly, and so it's rarely used in game programming.

There are straightforward methods for detecting intersection between arbitrarily oriented shapes. One of the most commonly used methods is the SAT (separating axis test), which can be used to test for intersection between convex polytopes (which includes line segments and boxes, among other things).

##### Share on other sites
If your objects are geometric shapes you can use much better algorithms.

for example hittesting a line and circle. it finds the closest point on line to the center of circle and test if it is smaller than radius (based on this algorithm http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/)

int testCircleLine(float p1[2], //first point of line                   float p2[2], //second point of line                   float c[2],  //center of circle                    float r     //radius of center                  ){float v1[2], v2[2],  t, temp, xdiff, ydiff;float closest[2];v1[0] = r[0] - p1[0]; //v1 = r - p1v1[1] = r[1] - p1[1];v2[0] = p2[0] - p1[0]; //v2 = Normal(p2 - p1)v2[1] = p2[1] - p1[1];temp = sqrt(v2[0]*v2[0] + v2[1]*v2[1]);v2[0] /= temp;v2[1] /= temp;t = v1[0]*v2[0] + v1[1]*v2[1]; //dotproduct(v1, v2)if(t < 0.0){  closest[0] = p1[0]; //if t is smaller than 0.0,   closest[1] = p1[1]; //closest point is at the left of first point                      //use first point instead}else if(t > 1.0){  closest[0] = p2[0]; //closest point is at the right side of second point  closest[1] = p2[1]; //use the second point}else{  closest[0] = p1[0] + v2[0]*t; //find the closest point center of the circle   closest[1] = p1[1] + v2[1]*t;}xdiff = closest[0] - c[0];ydiff = closest[1] - c[1];if( sqrt(xdiff*xdiff + ydiff*ydiff) < r){   return 1;//if distance smaller than r return 1}else{  return 0; //else return 0}}

##### Share on other sites
for testing two rectangle hits each other, here is another algorithm.

this one tests if two lines intersects. first it finds the intersection of two lines and after that check if this point is between input points

int test2lines(float p1[2], float p2[2], float q1[2],float  q2[2]){float m1, n1, m2, n2, xInt, yInt//y = mx+ n << find m and n for both linesfloat m1 = (p2[1] - p1[1])/(p2[0] - p1[0]);float n1 = p1[1] - m1*p1[0];float m2 = (q2[1] - q1[1])/(q2[0] - q1[0]);float n2 = q1[1] - m2*q1[0];if(m1 == m2) return 0; //if they are paralel no intersection// m1x + n1 = m2x + n1 << find xxInt = (n2 - n1)/(m1 - m2); yInt = m1*xInt + n1; //then find y//check if this point between p1-p2 and q1-q2if(p1[0] < p2[0]){  if(xInt < p1[0] || xInt > p2[0]) return 0;}else{  if(xInt > p1[0] || xInt < p2[0]) return 0;}if(p1[1] < p2[1]){  if(xInt < p1[1] || xInt > p2[1]) return 0;}else{  if(xInt > p1[1] || xInt < p2[1]) return 0;}if(q1[0] < q2[0]){  if(xInt < q1[0] || xInt > q2[0]) return 0;}else{  if(xInt > q1[0] || xInt < q2[0]) return 0;}if(p1[1] < q2[1]){  if(xInt < q1[1] || xInt > q2[1]) return 0;}else{  if(xInt > q1[1] || xInt < q2[1]) return 0;}return 1;}

I am note sure about last part but it should work

##### Share on other sites
What kind of objects needs to collide against the rotated rectangle?

Most collisions can be based on the basic point-to-line distance functions. For example, when you check if a point is inside your normal rectangle, you probably do something like the following:
if(x > leftx && x < rightx) is inside on the x axis

This can be translated to the following, where you have two edges, the left and the right edge of the rectangle.
distance to left side = leftx - xdistance to right side = x - rightxif(both distances < 0) is inside on the x axis

This works by letting each edge have a 'front side', and a 'back side', where the distance is negative 'behind' the edge, and positive 'in front of' the edge, and we decide that the front side is pointing to the outside of the box. The same can be done for distance to the horizontal edges with the y-coordinate, so when the distance is negative to all edges, then a point is inside the box.

The same type of distance can be used for every line, not just horizontal and vertical lines. By using a representation for the line like in the image below, we can decide the distance to it.

To get a line like this, you need the end-points (x0,y0) and (x1,y1), which should be easy since I guess your box has 4 corner points. The way this works is that when starting at (x0,y0) and looking towards (x1,y1), the 'front side' of the line, with positive distance, is to the right of the line. So by switching order of the end-points you get that the other side of the line is the front.
When you have two end-points you can calculate the 'normal' (nx,ny). It is done in the following way:
nx = y0 - y1ny = x1 - x0

This can also be used to get the actual distance from the line to a point. In the simple case of a vertical line and 'distance = x - x0', you get the distance as the number of pixels from the line to the point. In the case of the diagonal line you will always get a correct positive or negative distance, so you know the side, but if you want the actual distance you also need to 'normalize' the normal, like the following (requires floating point numbers):
nx = y0 - y1ny = x1 - x0length = sqrt(nx*nx + ny*ny)nx /= lengthny /= length

Or just divide the distance by the length of the normal after the calculation.

##### Share on other sites
Quote:
 Original post by shultaysIf your objects are geometric shapes you can use much better algorithms. for example hittesting a line and circle. it finds the closest point on line to the center of circle and test if it is smaller than radius (based on this algorithm http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/)

I actually really wanted to do this. I just wasn't sure how. I haven't yet taken the time to fiddle with the geometry on paper.

At the moment I have balls bouncing around a stationary rectangle. When a ball hits a wall, I want the rectangle to rotate. At the moment I have, I am testing the radius of the ball against the distance from the wall.

I want to clarify that the game is in 2-d

So the only difference between my code and your code is that the closest point on the rectangle with respect to the ball is unknown. Now I need to find this point.

I am going to read these posts a few times and post once I understand them.

also, I was wondering if I could simply rotate the entire game and then test how far the balls are from the x and y boundaries of the rectangle. Would this be a very expensive operation?

Correct?

##### Share on other sites
EDIT: Was having a serious brain fart. Figured it out

So I think I understand what's going on. The only question I have is how to do I find the vertices of the rectangle?

I know the initial coordinates of each vertex of the rectangle and the amount in radians that each vertex has rotated. I next need to use the knowledge of the angle of rotation to find how much each vertex has shifted. This new vertex can be used as the second point of the line that I'm looking for.

All I know is that they will lay along the boundary of some ellipse. (It isn't a circle because a rectangle is rotating, not a square.)

Ideas?

Thank you

[Edited by - zoner7 on July 23, 2009 10:21:59 PM]

##### Share on other sites
It's still a circle.
To rotate a point around the origin (counter clockwise when y increases downwards and x to the right) you do:
newx = x * cos(angle) + y * sin(angle)newy = y * cos(angle) - x * sin(angle)

If you have an original point on the rectangle (x, y), rotating around the rectangle's center point (cx, cy), then you can get the new coordinates as follows:
newx = cx + (x - cx) * cos(angle) + (y - cy) * sin(angle)newy = cy + (y - cy) * cos(angle) - (x - cx) * sin(angle)

##### Share on other sites
hmm... not quite sure if I did something different that your last post does. about your last post. I'm pretty positive that what I did is right.

Anyhow. I messed up somewhere along the way. The balls simply go right through the walls.

I think I did something wrong in my calculation of u. Unfortunately, I still haven't figured out how to use VS's debugger.

here is my code:

It looks long, but it simply repeats the same operation four times, once time for each line. I would really appreciate a little guidance. Thanks a ton.

By the way, the call of this function is inside a for loop that tests every ball.

[source lang = c++]void PlayGameState::WallCollision (vector <Ball>:: iterator iter)	{		double u;		//Starting from the upper left vertice and going clockwise, ending at the lower left vertice.		//This finds the coordinates of each vertex based on the given rotation.		Vector2d vertice1 (radius * cos(rotationPos) + 200, radius * sin(rotationPos) + 220);  //200 and 220 are the coorinates of the center of the box.		Vector2d vertice2 (radius * cos(rotationPos + PI) + 200, radius * sin(rotationPos + PI) + 220);					Vector2d vertice3 (radius * cos(rotationPos + 3/2 * PI) + 200, radius * sin(rotationPos + 3/2 * PI) + 220);		Vector2d vertice4 (radius * cos(rotationPos + 2 * PI) + 200, radius * sin(rotationPos + 2 * PI) + 220);		Vector2d testPoint;		// Find the closest point on  every line to the ball (iter).		// Take dot product between position vector and relative velocity vector //		// which velocities reverse depends on the orientation of the wall.		// If rotationPos = 0, then we use the calculations we used for stationay collision testing.		// we will determine which wall is which by using vertices.		u = ( ((*iter).Pos().x - vertice1.x) * (vertice2.x - vertice1.x) + ((*iter).Pos().y - vertice1.y) * (vertice2.y - vertice1.y) ) / Distance(vertice1, vertice2);		if ( u < 1 && u > 0)		{			testPoint.x = vertice1.x + u * (vertice2.x - vertice1.x);			testPoint.y = vertice1.y + u * (vertice2.y - vertice1.y);			if ( Distance((*iter).Pos(), testPoint) <= 29 )			{				//1st and 2nd vertice means top wall... need to find orientation by looking at rotationPos				if (rotationPos != 0)				{					(*iter).Vel( - (*iter).Vel() );				}				else (*iter).Vel(Vector2d((*iter).Vel().x, -(*iter).Vel().y));				game.hge->Effect_Play(WallCollisionEffect);				CalculateRotation(iter);				//occasionally there is sticking.  Under these circumstances, 				//we want to move theq ball back into the rectangle to avoid infinite collision detection				(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());			}		}			u = ( ((*iter).Pos().x - vertice3.x) * (vertice4.x - vertice3.x) + ((*iter).Pos().y - vertice3.y) * (vertice4.y - vertice3.y) ) / Distance(vertice3, vertice4);		if ( u < 1 && u > 0)		{			testPoint.x = vertice3.x + u * (vertice4.x - vertice3.x);			testPoint.y = vertice3.y + u * (vertice4.y - vertice3.y);			if ( Distance((*iter).Pos(), testPoint) <= 29 )			{				//3rd and 4th vertices means bottom wall.				if (rotationPos != 0)				{					(*iter).Vel( - (*iter).Vel() );				}				else (*iter).Vel(Vector2d((*iter).Vel().x, -(*iter).Vel().y));				game.hge->Effect_Play(WallCollisionEffect);				CalculateRotation(iter);				//occasionally there is sticking.  Under these circumstances, 				//we want to move the ball back into the rectangle to avoid infinite collision detection				(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());			}		}		u = ( ((*iter).Pos().x - vertice2.x) * (vertice3.x - vertice2.x) + ((*iter).Pos().y - vertice2.y) * (vertice3.y - vertice2.y) ) / Distance(vertice2, vertice3);		if ( u < 1 && u > 0)		{			testPoint.x = vertice2.x + u * (vertice3.x - vertice2.x);			testPoint.y = vertice2.y + u * (vertice3.y - vertice2.y);			if ( Distance((*iter).Pos(), testPoint) <= 29 )			{				//2nd and 3rd vertices means right wall.				if (rotationPos != 0)				{					(*iter).Vel( - (*iter).Vel() );				}				else (*iter).Vel(Vector2d(-(*iter).Vel().x, (*iter).Vel().y));				game.hge->Effect_Play(WallCollisionEffect);				CalculateRotation(iter);				//occasionally there is sticking.  Under these circumstances, 				//we want to move the ball back into the rectangle to avoid infinite collision detection				(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());			}		}					u = ( ((*iter).Pos().x - vertice4.x) * (vertice1.x - vertice4.x) + ((*iter).Pos().y - vertice4.y) * (vertice1.y - vertice4.y) ) / Distance(vertice4, vertice1);		if ( u < 1 && u > 0)		{			testPoint.x = vertice4.x + u * (vertice1.x - vertice4.x);			testPoint.y = vertice4.y + u * (vertice1.y - vertice4.y);			if ( Distance((*iter).Pos(), testPoint) <= 29 )			{				//1st and 4th vertices means left wall.				if (rotationPos != 0)				{					(*iter).Vel( - (*iter).Vel() );				}				else (*iter).Vel(Vector2d(-(*iter).Vel().x, (*iter).Vel().y));				game.hge->Effect_Play(WallCollisionEffect);				CalculateRotation(iter);				//occasionally there is sticking.  Under these circumstances, 				//we want to move the ball back into the rectangle to avoid infinite collision detection				(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());			}		}	}

EDIT: changed the order of the vertex arguments in the distance formula. They were backwards. The program still does not work, however

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013707
×