Java-Gaming.org
 Featured games (81) games approved by the League of Dukes Games in Showcase (497) Games in Android Showcase (114) games submitted by our members Games in WIP (563) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Collision Detection: Circle to Rectangle  (Read 4872 times) 0 Members and 1 Guest are viewing this topic.
Serethos

Junior Member

Java games rock!

 « Posted 2005-07-25 18:10:33 »

I need a fine collision detection method for a circle against a rectangle.
i read the tutorial from HarveyCartel http://www.harveycartel.org/metanet/tutorials/tutorialA.html

But i dont understand it, especially the point how to know which corner of the rectangle to take
for testing. some explanation or another method would make me happy ...
anarchotron

Junior Member

...precious bodily fluids.

 « Reply #1 - Posted 2005-07-25 18:58:24 »

Are your rectangles axis-aligned?

If so, just check the distance of the circle from the center of the rect.

CC = circle center
CR = circle radius

RC = rect center
RH = rect height
RW = rect width

if abs(CC.x - RC.x) <= (RW/2 + CR)  then collision
if abs(CC.y - RC.y) <= (RH/2 + CR) then collision

If the rect is not axis aligned, you can transform the circle's center into a space centered and aligned with the rectangle, and then do the above.

Alan_W

JGO Knight

Medals: 8
Projects: 3

Java tames rock!

 « Reply #2 - Posted 2005-07-25 20:26:13 »

Are you sure about that.  Draw a square.  Now draw a circle just not touching the bottom left corner of the square at the 45 degree angle from the top.   See what I mean.  What you've got there is a rectangle against square collision detector.

Alan

Edit:  Here's an idea.  I'm going to describe it graphically, rather than programmatically.  I am assuming the rectangle is aligned with the x & y axes.  If not, then a rotation is required first.

1) Draw two lines parallel with the x and y axes, through the centre of the circle, splitting it into four quadrants.  The lines extend beyond the circle.
2) Determine which quadrant each corner of the rectangle lies in.
3) i) If 3 or 4 quadrants have at least one corner, then there is a collision
3 ii) If 2 quadrants have at least one corner then check if the square bounding box of the circle intersects the rectangle.  If so then there is a collision
3 iii) If all rectangle points fall in the same quadrant, then calculate the square of the distance of each rectangle corner from the centre of the circle.  If any of these are less than the square of the circle radius then there is a collision.

It's just an idea,  may be a better way;)

Time flies like a bird. Fruit flies like a banana.
 Games published by our own members! Check 'em out!
anarchotron

Junior Member

...precious bodily fluids.

 « Reply #3 - Posted 2005-07-25 21:35:05 »

Doh!  You're right.

Hehehe
Jeff

JGO Coder

Got any cats?

 « Reply #4 - Posted 2005-07-25 22:25:45 »

Hmm./ just off the top of my head, thre may be a better way...

Aumming axis alingment...

(1) Do pt v. circle for all 4 corners of the rect.  Thats cehap and will get you everything but the case where the circle is wholly
enclosed in the rect.

(2) Do circle center v. rectangle tofind that one case.

As I loo kat this, It *might* be slightly  faster to reverse the tests above, but im not sure it matters much.

There is also probably a heuristic possible here doing distance of center to center to eliminate most cases. Again not sure if the distance calc is woth it.  (Might be if you did it in distance-squared space to avoid the sqrt...)

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
tom
 « Reply #5 - Posted 2005-07-25 22:39:07 »

Hmm./ just off the top of my head, thre may be a better way...

Aumming axis alingment...

(1) Do pt v. circle for all 4 corners of the rect.  Thats cehap and will get you everything but the case where the circle is wholly
enclosed in the rect.

(2) Do circle center v. rectangle tofind that one case.

As I loo kat this, It *might* be slightly  faster to reverse the tests above, but im not sure it matters much.

There is also probably a heuristic possible here doing distance of center to center to eliminate most cases. Again not sure if the distance calc is woth it.  (Might be if you did it in distance-squared space to avoid the sqrt...)

It's not enough to only check the points of the rectangle against the circle. The circle can still intersects one of the sides of the rectangle. A slow and easy way would be to check if any of the four linesegments intersects the sircle.

oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #6 - Posted 2005-07-25 23:35:24 »

java.awt.geom.Ellipse2D has a good/fast intersects method.

Alan_W

JGO Knight

Medals: 8
Projects: 3

Java tames rock!

 « Reply #7 - Posted 2005-07-26 04:48:12 »

It's not enough to only check the points of the rectangle against the circle. The circle can still intersects one of the sides of the rectangle. A slow and easy way would be to check if any of the four linesegments intersects the sircle.

I did line segment against circle for something at work.  It works fine, but requires solving a quadratic for the general case (arbitrary line).  You need to solve in x or solve in y according to the line gradient to avoid divide by zero. There's also some additional testing (using dot products) to see if any potential intersection occurs beyond the endpoints of the line.  Hopefully this would simplify a bit for lines which are only vertical or horizontal.

For the case of rectangle against circle, there is also the case where the rectangle completely surrounds the circle (or vice versa), although it may not be necessary to test for this, depending on the application.

Alan

Edit.  After a bit more thought, I think that the method I outlined earlier will be a fair bit quicker then doing 4 line to circle checks:

Something like this untested code.  (Only the two diagonally opposite corners of the rectangle are stored)
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50 `private boolean[][] quadrant = new boolean[2][2];public boolean collision(Rectangle rectangle, Circle circle) {  // Clear quadrant flags  for (int x=0; x++; x<2)    for(int y=0; y++; y<2)      quadrant[x][y] = false;  // Determine quadrant of each corner  for (int x=0; x++; x<2)  {    int quadX = ?(rectangle.x[x]>=circle.x)0:1;    for(int y=0; y++; y<2) {      int quadY = ?(rectangle.y[y]>=circle.y)0:1;      quadrant[quadX][quadY] = true;    }  }  // Count the number of quadrants with at least one corner  int quadrants = 0;  for (int x=0; x++; x<2)    for(int y=0; y++; y<2)      if (quadrant[x][y])        quadrants++;  // Detect Collisions  boolean collision = false;  switch (quadrants) {    case 1: // Check each rectangle corner against circle radius      float radiusSquared = circle.radius*circle.radius;      for (int x=0; x++; x<2) {        float dx = rectangle.x[x] - circle.x;        for(int y=0; y++; y<2) {          float dy = rectangle.y[y] - circle.y;          if (dx*dx+dy*dy <= radiusSquared)            collision = true;        }      }         break;    case 2: // Check for intersection between rectangle and bounding box of the circle      boolean intersectX = !(rectangle.x[1] < circle.x-circle.radius || rectangle.x[0] > circle.x+circle.radius);      boolean intersectY = !(rectangle.y[1] < circle.x-circle.radius || rectangle.y[0] > circle.x+circle.radius);      if (intersectX && intersectY)        collision = true;      break;    default: // Anything else is a collision      collision = true;  }  return collision;}`

/Edit - Corrected an error in the rectangle arrays

Time flies like a bird. Fruit flies like a banana.
Jeff

JGO Coder

Got any cats?

 « Reply #8 - Posted 2005-07-28 04:55:20 »

I should mention that, when Im faced with any geometric problem like this in my code,I generally reach for my set of Graphics Gems volumes.

Books no serious graphics programmer should be without.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Serethos

Junior Member

Java games rock!

 « Reply #9 - Posted 2005-07-28 20:27:30 »

I would love to buy the whole XXX Gems series, but i never know, which one to take (no. 1-798)
and they're quite expensive. i have here two game programming books - with a serious lack on
collision detection - and a java reference. these books alone shot a hole in my pocket.
but can you suggest one special book of the series? amazon shows at least three of them ..
 Games published by our own members! Check 'em out!
Orangy Tang

JGO Kernel

Medals: 56
Projects: 11

Monkey for a head

 « Reply #10 - Posted 2005-07-28 21:00:33 »

Eberly's "3d game engine design" is very good for collision detection routines. Covers practically all intersection cases with both equations and code. Very maths heavy though, and lots of formal maths notation.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Jeff

JGO Coder

Got any cats?

 « Reply #11 - Posted 2005-08-02 01:16:09 »

I would love to buy the whole XXX Gems series, but i never know, which one to take (no. 1-798)
and they're quite expensive. i have here two game programming books - with a serious lack on
collision detection - and a java reference. these books alone shot a hole in my pocket.
but can you suggest one special book of the series? amazon shows at least three of them ..

Graphics Gems is where it all started.  For fundemental fast geometric tricks Id say the first 3 or so volumes are what i find msyelf referring back to a lot when writing geometric code.  You at lesat used to be able to buy most of the set on a single CD.  I dont find that as useful as I really like paper for my refernces, but I think it was significantly cheaper then buying all the books.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 BurntPizza (24 views) 2014-09-19 03:14:18 Dwinin (39 views) 2014-09-12 09:08:26 Norakomi (68 views) 2014-09-10 13:57:51 TehJavaDev (93 views) 2014-09-10 06:39:09 Tekkerue (47 views) 2014-09-09 02:24:56 mitcheeb (68 views) 2014-09-08 06:06:29 BurntPizza (51 views) 2014-09-07 01:13:42 Longarmx (38 views) 2014-09-07 01:12:14 Longarmx (44 views) 2014-09-07 01:11:22 Longarmx (40 views) 2014-09-07 01:10:19
 BurntPizza 37x Riven 18x Rayvolution 18x ags1 16x princec 16x basil_ 16x KevinWorkman 15x LiquidNitrogen 12x kevglass 12x theagentd 11x nsigma 11x deathpat 10x HeroesGraveDev 9x The Lion King 7x Gibbo3771 6x cylab 6x
 List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50List of Learning Resources2014-07-31 16:26:06List of Learning Resources2014-07-31 11:54:12HotSpot Optionsby dleskov2014-07-08 01:59:08
 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