circle-circle collision

Solution 1:

Collision between circles is easy. Imagine there are two circles:

C1 with center (x1,y1) and radius r1;
C2 with center (x2,y2) and radius r2.

Imagine there is a line running between those two center points. The distance from the center points to the edge of either circle is, by definition, equal to their respective radii. So:

if the edges of the circles touch, the distance between the centers is r1+r2;
any greater distance and the circles don't touch or collide; and
any less and then do collide.

So you can detect collision if:

(x2-x1)^2 + (y2-y1)^2 <= (r1+r2)^2

meaning the distance between the center points is less than the sum of the radii.

The same principle can be applied to detecting collisions between spheres in three dimensions.

Edit: if you want to calculate the point of collision, some basic trigonometry can do that. You have a triangle:

        (x1,y1)
        |\
        | \
        |  \ sqrt((x2-x1)^2 + (y2-y1)^2) = r1+r2
|y2-y1| |   \
        |    \
        |   X \
(x1,y2) +------+ (x2,y2)
         |x2-x1|

The expressions |x2-x1| and |y2-y1| are absolute values. So for the angle X:

        |y2 - y1|
sin X =  -------
         r1 + r2

        |x2 - x1|
cos X =  -------
         r1 + r2

        |y2 - y1|
tan X =  -------
        |x2 - x1|

Once you have the angle you can calculate the point of intersection by applying them to a new triangle:

  +
  |\
  | \
b |  \ r2
  |   \
  |  X \
  +-----+
     a

where:

        a
cos X = --
        r2

a = r2 cos X

From the previous formulae:

       |x2 - x1|
a = r2 -------
        r1 + r2

Once you have a and b you can calculate the collision point in terms of (x2,y2) offset by (a,b) as appropriate. You don't even need to calculate any sines, cosines or inverse sines or cosines for this. Or any square roots for that matter. So it's fast.

But if you don't need an exact angle or point of collision and just want the octant you can optimize this further by understanding something about tangents, which is:

0 <= tan X <= 1 for 0 <= X <= 45 degrees;
tan X >= 1 for 45 <= X <= 90
0 >= tan X >= -1 for 0 >= X => -45;
tan X <= -1 for -45 >= X => -90; and
tan X = tan (X+180) = tan (X-180).

Those four degree ranges correspond to four octants of the cirlce. The other four are offset by 180 degrees. As demonstrated above, the tangent can be calculated simply as:

        |y2 - y1|
tan X =  -------
        |x2 - x1|

Lose the absolute values and this ratio will tell you which of the four octants the collision is in (by the above tangent ranges). To work out the exact octant just compare x1 and x2 to determine which is leftmost.

The octant of the collision on the other single is offset (octant 1 on C1 means octant 5 on C2, 2 and 6, 3 and 7, 4 and 8, etc).

Solution 2:

As cletus says, you want to use the sum of the radii of the two balls. You want to compute the total distance between the centers of the balls, as follows:

Ball 1:  center: p1=(x1,y1)  radius: r1
Ball 2:  center: p2=(x2,y2)  radius: r2

collision distance: R= r1 + r2
actual distance:    r12= sqrt( (x2-x1)^2 + (y2-y1)^2 )

A collision will happen whenever (r12 < R). As Artelius says, they shouldn't actually collide on the x/y axes, they collide at a particular angle. Except, you don't actually want that angle; you want the collision vector. This is the difference between the centers of the two circles when they collide:

collision vector: d12= (x2-x1,y2-y1) = (dx,dy)
actual distance:  r12= sqrt( dx*dx + dy*dy )

Note that you have already computed dx and dy above when figuring the actual distance, so you might as well keep track of them for purposes like this. You can use this collision vector for determining the new velocity of the balls -- you're going to end up scaling the collision vector by some factors, and adding that to the old velocities... but, to get back to the actual collision point:

collision point:  pcollision= ( (x1*r2+x2*r1)/(r1+r2), (y1*r2+y2*r1)/(r1+r2) )

To figure out how to find the new velocity of the balls (and in general to make more sense out of the whole situation), you should probably find a high school physics book, or the equivalent. Unfortunately, I don't know of a good web tutorial -- suggestions, anyone?

Oh, and if still want to stick with the x/y axis thing, I think you've got it right with:

if( abs(dx) > abs(dy) ) then { x-axis } else { y-axis }

As for why it might fail, it's hard to tell without more information, but you might have a problem with your balls moving too fast, and passing right by each other in a single timestep. There are ways to fix this problem, but the simplest way is to make sure they don't move too fast...

Solution 3:

This site explains the physics, derives the algorithm, and provides code for collisions of 2D balls.

Calculate the octant after this function calculates the following: position of collision point relative to centre of mass of body a; position of collision point relative to centre of mass of body a

/**
This function calulates the velocities after a 2D collision vaf, vbf, waf and wbf from information about the colliding bodies
@param double e coefficient of restitution which depends on the nature of the two colliding materials
@param double ma total mass of body a
@param double mb total mass of body b
@param double Ia inertia for body a.
@param double Ib inertia for body b.
@param vector ra position of collision point relative to centre of mass of body a in absolute coordinates (if this is
                 known in local body coordinates it must be converted before this is called).
@param vector rb position of collision point relative to centre of mass of body b in absolute coordinates (if this is
                 known in local body coordinates it must be converted before this is called).
@param vector n normal to collision point, the line along which the impulse acts.
@param vector vai initial velocity of centre of mass on object a
@param vector vbi initial velocity of centre of mass on object b
@param vector wai initial angular velocity of object a
@param vector wbi initial angular velocity of object b
@param vector vaf final velocity of centre of mass on object a
@param vector vbf final velocity of centre of mass on object a
@param vector waf final angular velocity of object a
@param vector wbf final angular velocity of object b
*/
CollisionResponce(double e,double ma,double mb,matrix Ia,matrix Ib,vector ra,vector rb,vector n,
    vector vai, vector vbi, vector wai, vector wbi, vector vaf, vector vbf, vector waf, vector wbf) {
  double k=1/(ma*ma)+ 2/(ma*mb) +1/(mb*mb) - ra.x*ra.x/(ma*Ia) - rb.x*rb.x/(ma*Ib)  - ra.y*ra.y/(ma*Ia)
    - ra.y*ra.y/(mb*Ia) - ra.x*ra.x/(mb*Ia) - rb.x*rb.x/(mb*Ib) - rb.y*rb.y/(ma*Ib)
    - rb.y*rb.y/(mb*Ib) + ra.y*ra.y*rb.x*rb.x/(Ia*Ib) + ra.x*ra.x*rb.y*rb.y/(Ia*Ib) - 2*ra.x*ra.y*rb.x*rb.y/(Ia*Ib);
  double Jx = (e+1)/k * (Vai.x - Vbi.x)( 1/ma - ra.x*ra.x/Ia + 1/mb - rb.x*rb.x/Ib)
     - (e+1)/k * (Vai.y - Vbi.y) (ra.x*ra.y / Ia + rb.x*rb.y / Ib);
  double Jy = - (e+1)/k * (Vai.x - Vbi.x) (ra.x*ra.y / Ia + rb.x*rb.y / Ib)
     + (e+1)/k  * (Vai.y - Vbi.y) ( 1/ma - ra.y*ra.y/Ia + 1/mb - rb.y*rb.y/Ib);
  Vaf.x = Vai.x - Jx/Ma;
  Vaf.y = Vai.y - Jy/Ma;
  Vbf.x = Vbi.x - Jx/Mb;
  Vbf.y = Vbi.y - Jy/Mb;
  waf.x = wai.x - (Jx*ra.y - Jy*ra.x) /Ia;
  waf.y = wai.y - (Jx*ra.y - Jy*ra.x) /Ia;
  wbf.x = wbi.x - (Jx*rb.y - Jy*rb.x) /Ib;
  wbf.y = wbi.y - (Jx*rb.y - Jy*rb.x) /Ib;
}

Solution 4:

I agree with provided answers, they are very good.
I just want to point you a small pitfall: if the speed of balls is high, you can just miss the collision, because circles never intersect for given steps.
The solution is to solve the equation on the movement and to find the correct moment of the collision.

Anyway, if you would implement your solution (comparisons on X and Y axes) you'd get the good old ping pong! http://en.wikipedia.org/wiki/Pong
:)

Solution 5:

The point at which they collide is on the line between the midpoints of the two circles, and its distance from either midpoint is the radius of that respective circle.