2

I want to detect Collision between circle shape and rectangle shape, but dont know how.

I know how to detect Collision between circle to circle using pythagorean theorem which is:

(x2 - x1)^2 + (y2 - y1)^2 - (r2 + r1) , but what is the math to detect Collision

between circle shape and rectangle shape in C or C++ programming language.

anna Sjolvikaz
  • 141
  • 1
  • 1
  • 8
  • Maybe you want to test for collision between polygons instead? ;) – Shark Apr 05 '13 at 11:52
  • What did you try? Have you identifed *any* tests that might be part of detecting this? – unwind Apr 05 '13 at 11:52
  • Shark polygons would be also usefull, but i dont know how - unwind that why i'm asking for help, becouse i dont knot where to start – anna Sjolvikaz Apr 05 '13 at 11:53
  • What exactly you want? DO you want just some algorithm to detect collision or do you want good one or even best one? What did you try? If you want just any way to detect it why you don't want to take steps you do to find this collision with a pen and a paper? – JustAnotherCurious Apr 05 '13 at 11:58
  • i want some algorithm to detect collision – anna Sjolvikaz Apr 05 '13 at 11:59
  • Depending on what you actually doing, collision detection can mean different things. Are your shapes moving? Do you want to know a point of collision and what are force momenta? For simple case you can just test whether your circle is intersecting with rectangle by testing each segment making the rectangle. – Archie Apr 05 '13 at 11:59
  • I have already looked at this and read, but could't understand it – anna Sjolvikaz Apr 05 '13 at 12:04
  • 3
    @annaSjolvikaz "i want some algorithm to detect collision" then why don't you want to sit with the pen and paper and detect some cases with you own head and hands and then just program the way you detected it by yourself? – JustAnotherCurious Apr 05 '13 at 12:12
  • here is the answer http://stackoverflow.com/a/15906186/1329187 –  Apr 09 '13 at 15:34

4 Answers4

8

In collision detection it is often beneficial to first detect collisions between simple objects and then specialise to the more complex one. This is called broad-phase and narrow-phase collision detection. The idea is that using a simpler algorithm to rule out collisions first makes the process faster when objects can be proven trivially not to be colliding.

You could initially model all objects as circles or boxes that encompass the, potentially more complex, true shape. If you find that these objects are colliding then you can use a more complex algorithm to check for collisions.

It is known that, for all convex objects, if the two objects are not colliding then you can find a plane between them. This is known as the separating axis theorem. Since both a circle and a square are convex you can use this to design an algorithm to detect collisions between them.

You can first search simple planes, such as those parallel to the edges of the square and those that are tangents to the circle. A good choice would be the plane that is a tangent to the circle on the line between the two centres of the objects, followed by the line between the centre of the circle and each corner.

Once you have found a separating plane the objects can't be colliding and you can stop searching.

Hope this helps.

(A very detailed explanation of the application of this can be found here: http://www.metanetsoftware.com/technique/tutorialA.html#section1)

Will
  • 4,585
  • 1
  • 26
  • 48
3

A circle intersects a rectangle if the centre of the circle is inside the rectangle or if the distance from the centre of the circle to the closest point on the border of the rectangle is less than the radius of the circle. There are nine possibilities for the location of the centre of the circle relative to the rectangle, depending on where it lies relative to its extended sides:

A|B|C
-+-+-
D|E|F
-+-+-
G|H|I

In case E, clearly the circle and rectangle intersect. In cases A, C, G, I you need to test the distance to the closest corner. In the remaining cases use point-line distance from the centre of the circle to the nearest edge.

ecatmur
  • 152,476
  • 27
  • 293
  • 366
1

One solution is to turn the rectangle into four line segments, then test for intersections of those.

In pseudo-code:

for line in line-segments(rectangle)
   if line.end1 inside circle or line.end2 inside circle
       return true
   if line intersects circle
       return true
return false

This gives two types of tests:

  1. point in circle -- this is straightforward, a distance from the center of the circle
  2. line segment intersection with a circle -- this is a little more complex (example)
Drew Noakes
  • 300,895
  • 165
  • 679
  • 742
0

As they said before, divide your rectangle shape into lines and then intersect each line with the circle with the algorithms here.

Community
  • 1
  • 1
Quonux
  • 2,975
  • 1
  • 24
  • 32