Calculate x/y point that 2 moving balls will collide

I'm trying to make what is (essentially) a simple pool game, and would like to be able to predict where a shot will go once it hits another ball.

The first part is, I believe, to calculate if the cueball will hit anything, and if it does, where it collides. I can work out collision points for a line and a ball, but not 2 balls.

So given the x/y positions and velocities of 2 balls, how do I calculate the point at which they collide?

(PS: Im aware I can do this by calculating the distance between the two balls every step along the way, but I was hoping for something a little more elegant and optimal.)

Examp开发者_如何学JAVAle of setup: trying to calculate the red dot

http://dl.dropbox.com/u/6202117/circle.PNG

Some things to take note of:

• When two balls, each of radius r collide their centers are 2r apart.
• Your first ball can be assumed to travel in a straight line (well, first approximation, but start with this), and you can find the angle, alpha between this path and the direction from the first ball to the second.
• You know the center of the stationary ball, no?

Now you have some geometry to do.

Do this construction:

1. Mark the current center of the first (moving) ball as point A.
2. Mark the center of the stationary ball as point B.
3. Construct line segment AB.
4. Construct the ray, R, from A in the direction of movement.
5. Construct a circle of radius 2r around B.
6. Drop a segment from B perpendicular to R call the point of intersection C.
7. You know the distance AB and you can find the angle alpha between AB and R, with the Law of Sines find the length of BC.
8. From that length determine if there are 0, 1 or 2 solutions. If there are 0 or 1 you are done.
9. Construct point D where the circle meets R closer to A, and use the Law of Sines again to find the distance AD.
10. The point of collision is the midpoint of BD

and now you know everything.

Constructing efficient code from this is left as an exercise.

BTW-- This construction won't work if both balls are moving, but you can transform into a frame where one is stationary, solve it that way, then transform back. Just be sure to check that the solution is in the allowed area after the reverse transformation...

/ Physicists can't not make comments like this. I tried to resist. I really did.

Drawing of @dmckee's answer

Edit

Just in response to @ArtB necromancer's answer, the solutions for point D in the above graph could be written:

1/2 {(Ax+Bx+2 d Dx Cos[alpha]- Dx Cos[2 alpha]+ 2 Dy (Cos[alpha]-d) Sin[alpha]), 
     (Ay+By+2 d Dy Cos[alpha]- Dy Cos[2 alpha]- 2 Dx (Cos[alpha]-d) Sin[alpha])
     }  

Where

Dx = Ax - Bx 
Dy = Ay - By   

And

d = Sqrt[4 r^2 - (Dx^2 + Dy^2) Sin[alpha]^2]/Sqrt[Dx^2 + Dy^2]  

HTH!

I was looking at @dmckee's solution and it took me quite a lot of work to work through it. The following is my notes for those perhaps looking for a more practical answer, it is taken directly from his post so the credit goes to him/her, but any mistakes are mine. I usual a Pascal-like assigment operator (ie :=) to distinguish between showing my work and the actual necessary code. I'm using the standard Y = mX +b format and a quasi-oop notation. I do use BC for both the segment and the resulting line. That said, this should 'almost' be copy'n'paste-able Python code (remove ";", replace "sqrt" and "sqr" with proper versions, etc).

1. A.x and A.y are the x & y positions, A.r is A's radius, and A.v is the velocity with A.v.x being the x component of it and A.v.y being the y component of it.
2. B is the same but without the velocity (or more accurately, subtract the velocities of B from A so B is relatively speaking stationary).
3. AB.m := (b.y - a.y) / (b.x - a.x); AB.b := A.y - AB.m * A.x;
4. R.m := A.v.y / A.v.x; R.b := A.y - R.m * A.x;
5. not necessary
6. BC.m := -A.v.x/A.v.y; which is the standard equation for perpendicular slope, BC.b := B.y - BC.m * B.x; Now C is where AB meets BC so we know that they are equal so lets equate C.y so C.y == AB.m * C.x + AB.b == BC.m * C.x + BC.b; so C.x := (AB.m - BC.M) / (BC.b - AB.b); then just plug in C.x to get C.y := AB.m * C.x + AB.b;
7. You can ignore the sine law since we have AB and BC so we can just use the Pythagorean theorem to get the length of BC, BC.l := sqrt( sqr(B.x-C.x) + sqr(B.y-C.y) );
8. If BC.l > A.r + B.r, there are zero solutions, and these circles do not touch since C is A's paths perigee with respect toB. IfBC.l == A.r + B.r, there is only one solution, andC == D. Otherwise, ifBC.l < A.r + B.rthen there are two solutions. You can think of this as such, if there are zero solutions the bullet missed, if there is one the bullet grazed, and if there are two then there is both an entry and exit wound. The one closer toA` is the one we want.
9. 1. Now, the math gets ugly so I'll show my work just in case I do something wrong.
   2. D is a point on AC that is A.r + B.r (aka 2r) away from B so: sqrt( sqr(D.x - B.x) + sqr(D.y - B.y) ) == 2r
   3. Therefore sqr(D.x - B.x) + sqr(D.y - B.y) == 4*r*r. Now 2 variables (ie D.x and D.y) with one equation is trouble, but we also know that D is on the line AC so D.y == AC.m*D.x + AC.b.
   4. We can substitute for D.y giving sqr(D.x - B.x) + sqr(AC.m*C.x + AC.b - B.y) == 4*r*r.
   5. This expands into the lovely: sqr(D.x) + 2*D.x - sqr(B.x) + sqr(AC.m*D.x) + 2*AC.b*D.x - 2*AC.m*D.x*B.y + sqr(AC.b) - 2*AC.b*B.y + sqr(B.y) == 4*r*r (this is the part where I mostly likely made a mistake if I did at all).
   6. These terms we can collect (remember, at this point only D.x is unknown; the rest we can treat as if they were constants) to get sqr(D.x) + 2*D.x - sqr(B.x) + sqr(AC.m*D.x) + 2*AC.b*D.x - 2*AC.m*D.x*B.y + sqr(AC.b) - 2*AC.b*B.y + sqr(B.y) == 4*r*r
   7. Rewritten into the neater (sqr(D.x) + sqr(AC.m*D.x)) + ( 2*D.x + 2*AC.b*D.x - 2*AC.m*B.y*D.x ) + ( - sqr(B.x) + sqr(AC.b) - 2*AC.b*B.y + sqr(B.y) ) == 4*r*r which can be refactored to (1 + sqr(AC.m)) * sqr(D.x) + 2*( 1 + AC.b - AC.m*B.y ) * D.x + ( sqr(B.y) - sqr(B.x) + sqr(AC.b) - 2*AC.b*B.y - 4*r*r ) == 0
   8. This now fits nicely into the quadratic formula (ie x == (-bb +- sqrt( sqr(bb) - 4*aa*cc ) / 2*aa) (using aa to avoid confusion with earlier variables), with aa := 1 + sqr(AC.m);, bb := 2*( 1 + AC.b - AC.m*B.y );, and cc := sqr(B.y) - sqr(B.x) + sqr(AC.b) - 2*AC.b*B.y - sqr(A.r+B.r);.
   9. Now we might get two solution so lets save the parts using -bb/2aa +- sqrt(sqr(bb)-4*aa*cc)/2*aa: first_term := -bb/(2*a); and second_term := sqrt(sqr(bb)-4*aa*cc)/2*aa;.
   10. First solution D1.x = first_term + second_term; with D1.y = AC.m * D1.x + AC.b, and a second solution D2.x = first_term + second_term; with D2.y = AC.m * D2.x + AC.b.
   11. Find the distances to A: D1.l := sqrt( sqr(D1.x-A.x) + sqr(D1.y-A.y) ); and D2.l = sqrt( sqr(D2.x-A.x) + sqr(D2.y-A.y) ); (actually it is more efficient to skip both square roots, but it makes no difference).
   12. The closer one is one you want D := D1 if D1.l < D2. l else D2;.
10. 1. The midpoint of DB, lets call it E, is the collision (I don't know how this generalises if the radii aren't equal).
    2. So constuct the line DB.m := (B.y-D.y)/(B.x-D.x); and DB.b = B.y - DB.m*B.x;.
    3. We don't need the length to determine the length since it should be BD.l == A.r + B.r, so sqrt( sqr(E.x-B.x) + sqr(E.y-B.y) ) == B.r.
    4. Again, we can substitute for E because we know it's on BD so E.y == BD.m * E.x + BD.b, getting sqrt( sqr(E.x-B.x) + sqr(BD.m * E.x + BD.b-B.y) ) == B.r.
    5. Expanding into sqr(E.x) - 2*E.x*B.x + sqr(B.x) + sqr(BD.m)*sqr(E.x) + 2*BD.m*E.x*BD.b - 2*BD.m*B.y + sqr(B.y) - 2*BD.b*B.y + sqr(B.y) == sqr(B.r)
    6. Which collects into

    sqr(E.x) + sqr(BD.m)*sqr(E.x) + 2*BD.m*E.x*BD.b - 2*E.x*B.x + sqr(B.x) - 2*BD.m*B.y + sqr(B.y) - 2*BD.b*B.y + sqr(B.y) == sqr(B.r) (1 + sqr(BD.m)) * sqr(E.x) + 2*(BD.m*BD.b - B.x) * E.x + sqr(B.x) + sqr(B.y) - 2*BD.m*B.y + sqr(B.y) - 2*BD.b*B.y + sqr(B.y) - sqr(B.r) == 0 aa := (1 + sqr(BD.m)); bb := 2*(BD.m*BD.b - B.x); cc := sqr(B.y) - 2*BD.m*B.y + sqr(B.y) - 2*BD.b*B.y + sqr(B.y) - sqr(B.r);, quadratic formula, and then get your two points and choose the one closer to B.

I wish I was just whoring for karma or the necromancer badge, but I really needed to work this out and figured I'd share. Ugh, I think I need to lay down now.