Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (769) Games in Android Showcase (230) games submitted by our members Games in WIP (855) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Collision Detection for Circle and Rectangle (including rotated)  (Read 8131 times) 0 Members and 1 Guest are viewing this topic.
miga

Junior Devvie

Medals: 2
Projects: 1

 « Posted 2012-02-24 05:37:10 »

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.

Miga's Hobby Programming - http://www.migapro.com
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #1 - Posted 2012-02-24 05:58:54 »

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.

See my work:
OTC Software
StumpyStrust
 « Reply #2 - Posted 2012-02-24 06:00:57 »

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.

UprightPath
 « Reply #3 - Posted 2012-02-24 06:23:00 »

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 radius*radius > (cornerX - circleX)^2 + (cornerY - circleY)^2. If any are true, it's a corner collision.
(3,3): 4 > 2*2 + 2*2 = false
(4,4): 4 > 3*3 + 3*3 = false
(2,4): 4 > 1*1 + 3*3 = false
(3,5): 4 > 2*2 + 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.

Roquen

JGO Kernel

Medals: 518

 « Reply #4 - Posted 2012-02-24 13:47:38 »

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.

DzzD
 « Reply #5 - Posted 2012-02-24 14:48:13 »

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=CDx*CircleX+CDy*CircleY - (Cx*CDx+Cy*CDy);
distCircleY=CAx*CircleX+CAy*CircleY - (Cx*CAx+Cy*CAy);

then compute collsion circle pos if any
if(no corner collision ?) => definitly no collision

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

Roquen

JGO Kernel

Medals: 518

 « Reply #6 - Posted 2012-03-08 15:13:02 »

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
miga

Junior Devvie

Medals: 2
Projects: 1

 « Reply #7 - Posted 2012-03-14 07:25:07 »

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.

Miga's Hobby Programming - http://www.migapro.com
Pages: [1]
 ignore  |  Print

 EgonOlsen (1577 views) 2018-06-10 19:43:48 EgonOlsen (1661 views) 2018-06-10 19:43:44 EgonOlsen (1146 views) 2018-06-10 19:43:20 DesertCoockie (1574 views) 2018-05-13 18:23:11 nelsongames (1175 views) 2018-04-24 18:15:36 nelsongames (1666 views) 2018-04-24 18:14:32 ivj94 (2422 views) 2018-03-24 14:47:39 ivj94 (1632 views) 2018-03-24 14:46:31 ivj94 (2722 views) 2018-03-24 14:43:53 Solater (886 views) 2018-03-17 05:04:08
 Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20Deployment and Packagingby philfrei2018-08-19 23:54:46
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org