Collision Detection for Circle and Rectangle (including rotated)

Newbie & Debugging Questions
#1

Hello there.

I have been trying to understand how I can do a collision detection with circle and rectangles including rotated ones. After searching on the web, I came to an idea about using lines to represent a rectangle. If any of the lines intersect the circle, there is a collision.

The picture below is an example. Red points represent the closest point from the center of circle and the line. The blue line is the distance from closest point to center of circle. I need to compare the radius and this distance to determine the collision. I’m struggling to find out that closest point.

I also have searched on this forum, but I just couldn’t understand very well. This is one of the links I found from a post. http://www.c-program.com/c-g-a-faq1.html#q7

I would like to ask for help and not giving away the answers. Can anyone help me understand how to perform collision detection with circle and rectangle?

Thanks.

#2

Try thinking of it like an axis-aligned bounding box. For that you simply would need to see if the circle’s X is within the rectangle’s width and the Y is within the height. For a rotated rectangle against a circle, you can simply think of the entire graph rotating with the rectangle, so that it remains an AABB. So you’re using the relative X and Y with this rotated axis, but the comparison is the same. Does that help you wrap your brain around it?

Trying not to get too specific. There are other routes to go down too, I figured this was the simplest to understand.

#3

Well the best way to see if there is collision would be to check the distance of one point to another.

So your circle or rectangles center point with that of another. You then would add in your rectangles length/width and you circles radius.

Hope this did not give away too much.

Tip: look up the distance formula and note that you do not have to do the square-root.

#4

Let’s see, some Maths time. Let me see if I can come up with something that’ll work/be intelligent.

  1. Except for corners, a rectangle is most likely to collide against circle in such a way that a the impacting side forms a line tangent to circle.
    1.2) Since many impacts will occur at a line tangent to the circle, we can disregard angle in these cases.
    1.3) In these cases, a collision can be detected by just figuring out which edge is closest to the circle, then checking whether the distance from this edge is less-than-or-equal to the circle’s radius. (This can be done by finding the line perpendicular to the line formed by that edge of the rectangle, and then shifting it so that the line passes through the center of the circle.)
  2. Corners are a special case
    2.2) An impact against a corner can just be checked by seeing whether the distance from the center of the circle to the closest corner is less-than-or-equal to the circle’s radius.

So, you’d have four ‘lines’ that would be the lines perpendicular to the edges and then the four corners. So…

Let’s say we have Circle, r=2 at (1,1).
Then we have a rectangle with points (3,3), (4,4), (2,4), (3,5).

Check if the points intersect first. (Can do radiusradius > (cornerX - circleX)^2 + (cornerY - circleY)^2. If any are true, it’s a corner collision.
radiusradius = 22 = 4.
(3,3): 4 > 22 + 22 = false
(4,4): 4 > 33 + 33 = false
(2,4): 4 > 11 + 33 = false
(3,5): 4 > 22 + 4*4 = false

First we find the Parallel and Perpendicular lines for each edge. In this case, we want the ‘range’ of the Perpendicular line. We get that by finding the slope, then solving for B in Y=MX+B.
(3,3) - (4,4): Y = X and Y = -X + [6,8]
(2,4) - (3,5): Y = X - 2 and Y = -X + [6,8]
(4,4) - (2,4): Y = -X + 8 and Y = X + [0,2]
(4,4) - (2,4): Y = -X + 6 and Y = X + [0,2]

So then we take those two lines and plug in the center of the circle, and solve for B. B = 0 and B = 0. If B is between the bounds we found earlier then if there is a collision, it will be against that edge. In this case, we have Y = X + [0,2]. So then we just solve for the intersection of:

Y = X and Y = -X + 8 which is X = - X + 8, which means that X = 4. We plug that into Y = X, and get (4,4).
Y = X and Y = -X + 6 which is X = - X + 6, which means that X = 3. We plug that into Y = X, and get (3,3).

Check the distance of each (Treat it like the point before), which is radius*radius > (cornerX - circleX)^2 + (cornerY - circleY)^2.
We’ve already done this check earlier, since I picked a stupid box. But it should be fairly easy to solve most of these.

A lot of these formulas can be hard coded into objects, so that it shouldn’t be too difficult to write them, and shouldn’t be too costly to figure them out.

And this is probably more math than you needed to know. :smiley:

#5

Personally for these kinds a problems I tend to start by reducing the problem as much as possible and think in terms of implicit equations. So a circle is some point (the center) and the set of all points within some given distance (the radius). A rectangle is the set of points “inside” four bounding directed lines, where the lines are not independent. Two parallel pairs, each pair are orthogonal to the other and lines within a pair point in opposite directions. So a directed line can be described either by the generalize line equation: Ax+By+C = 0, where A,B & C are constants. When testing a point, the equation is zero for on the line and positive for one side and negative for the other. This can be rewritten in terms of vectors as d = dot(N,P-V), where ‘d’ is the distance, N is the direction, P is the test point and V is any point on the line. That equation can be expanded into d = dot(N,P) - dot(N,V) and dot(N,V) is a constant. Now if you think about looking an unrotated rectangle centered at the origin, then if the bottom line has N={-1,0}, which points to the “left”. All points above the line will test positive. Moving counterclockwise to the line on the left which points “up” {N=0,1} and all points to the right of it test positive, etc. for the two remaining ({1,0},{0,-1}). Now notice that the only “variable” part of the test object is dotting N with P and the relation between the various N’s. Each is cheap to test a ‘point’ against an unrotated rectangle about the origin. Now if we wanted to test a point against a unrotated rectangle not about the origin, we simply need to calculate a temp P which is the translation of the rectangle subtracted out. Call “C” the centroid of the rectangle, then P’ = P-C. Now for rotation? Do the same, unrotate the system (i.e. modify P again). Now you have a point against a rotated & translated rectangle. The reason to do it this way is that the rectangle is the more complicated object…so it’s often desirable to move the simpler to be terms of the more complex. Now there are two ways to deal with a circle, either directly or expanding the rectangle a la Minkowski addition.

#6

you can simplify a lot the problem by changing frame of reference for computation (in other terms compute collision from the rectangle point of view) this way the given problem “Collision Detection for Circle and Rectangle (including rotated)”
become “Computing collision for a moving circle with a static rectangle”

to do it easily if you rectangle is done with four points ABCD like this
A—B
| |
C—D

for each physics cycle compute circle position in the rectangle frame of reference :
x distance using the normalized vector CD and point C
y distance using the normalized vector CA and point C

this will give you the position of the circle in the rectangle frame of reference (from the rectangle point of view) where you can compute collision easily (as the rectangle is static : none rotated or translated)

something like (CD & CA normalized):
distCircleX=CDxCircleX+CDyCircleY - (CxCDx+CyCDy);
distCircleY=CAxCircleX+CAyCircleY - (CxCAx+CyCAy);

then compute collsion circle pos if any
if (distCircleX<-radius) => no collision
if (distCircleY<-radius) => no collision
if (distCircleY>CDlenght+radius) => no collision
if (distCircleY>CAlenght+radius) => no collision
if(no corner collision ?) => definitly no collision

and convert this collison pos from rectangle to original frame of reference

#7

Huh. I somehow missed DzzD’s response to this. Interestingly enough, we’re saying the same thing in different ways. I posted a more complete explanation for what I was saying here: http://www.java-gaming.org/topics/vectors-what-s-the-point/24307/msg/225743/view/topicseen.html#msg225743

#8

Everyone, thanks for the replies.

I haven’t had time to reply since I have been working on something else. Also, I need time to consider a solution I’m capable of implementing.

Thanks again.