Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
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 5248 times)
0 Members and 1 Guest are viewing this topic.
Offline Serethos

Junior Devvie




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 ...
Offline anarchotron

Junior Devvie




...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.



Offline Alan_W

JGO Knight


Medals: 8
Projects: 3


Java tames rock!


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

 Roll Eyes 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 Smiley

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!
Legends of Yore - The Casual Retro Roguelike
Offline anarchotron

Junior Devvie




...precious bodily fluids.


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

Doh!  You're right.

Hehehe
Offline 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
Offline 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.

Offline 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.

弾幕 ☆ @mahonnaiseblog
Offline 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  Grin

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.
Offline 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
Offline Serethos

Junior Devvie




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!
Legends of Yore - The Casual Retro Roguelike
Offline 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. Shocked

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline 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.

rwatson462 (32 views)
2014-12-15 09:26:44

Mr.CodeIt (23 views)
2014-12-14 19:50:38

BurntPizza (50 views)
2014-12-09 22:41:13

BurntPizza (84 views)
2014-12-08 04:46:31

JscottyBieshaar (45 views)
2014-12-05 12:39:02

SHC (59 views)
2014-12-03 16:27:13

CopyableCougar4 (58 views)
2014-11-29 21:32:03

toopeicgaming1999 (123 views)
2014-11-26 15:22:04

toopeicgaming1999 (114 views)
2014-11-26 15:20:36

toopeicgaming1999 (32 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!