Intersection on circle of vector originating inside circle

Question

I have a circle. Inside the circle is a point. I have a vector originating at this point. I'd like to know what point on the circle this vector intersects. Here is a drawing:

http://n4te.com/temp/circle.png http://n4te.com/temp/circle.png

The red dot is the point I am trying to determine.

I know these things: the center of the circle, the origin of the vector, and the direction of the vector.

I know this is basic stuff, but I'm still having trouble. Most of the Googlings bring me to line-circle collision, which is related but not quite the same. Thanks for any help you can provide!

Answer 1

Elementary vector algebra.

O — center of circle (vector)
r — its radius       (scalar)
A — origin of ray    (vector)
k — direction of ray (vector)

Solve (A + kt - O)² = r² for scalar t, choose positive root, and A + kt is your point.

Further explanation:

. is dot product, ² for a vector is dot product of the vector with itself. Expand LHS

(A + kt - O)² = (A - O)² + 2(k.(A - O))t + k²t².

The quadratic is k²t² + 2(k.(A - O))t + (A - O)² - r² = 0. In terms of your variables, this becomes (rayVX² + rayVY²)t² + 2(rayVX(rayX - circleX) + rayVY(rayY - circleY))t + (rayX - circleX)² + (rayY - circleY)² - r² = 0.

Answer 2

Much thanks to Anton Tykhyy for his detailed answer. This was the resulting Java code:

float xDiff = rayX - circleX;
float yDiff = rayY - circleY;
float a = rayVX * rayVX + rayVY * rayVY;
float b = 2 * (rayVX * (rayX - circleX) + rayVY * (rayY - circleY));
float c = xDiff * xDiff + yDiff * yDiff - r * r;
float disc = b * b - 4 * a * c;
if (disc >= 0) {
    float t = (-b + (float)Math.sqrt(disc)) / (2 * a);
    float x = rayX + rayVX * t;
    float y = rayY + rayVY * t;
    // Do something with point.
}