determining algorithm for calculating a point intersecting a circle where the segment crosses from inside to the outside of the circle

Question

I have a line segment between points A and B. A is inside a circle with a center at 0,0 with a radius of R. I am stumped trying to come up with an efficient way to calculate the intersection of line segment AB with this circle.

Answer 1

This is a mere second degree equation resolution

Line is y=A.x +B , where A and B are constants Circle is y^2=R^2 - x^2 , where R is the radius, and circle center is 0,0

so (A.x+B)^2=R^2-x^2 => A^2.x^2 +2.A.x.B +B^2 =R^2 -x^2 => (A^2+1).x^2 + 2.A.B.x +B^2-R^2 =0

The algorithm is :

let P=A^2+1 , G=2.A.B , H=B^2-R^2 The equation is : P.x^2 + G.x + H=0

that gives 3 cases depending on delta delta=G^2-4*P*H

If delta<0 => no intersections if delta=0 => intersect in 1 point : x=-G/2*P and y=Ax+B if delta>0 => intersect in 2 points : x1=(-G-sqrt(delta))/(2*P) , y1=Ax1+B and x2=(-G+sqrt(delta))/(2*P) ,y2=Ax2+B (where sqrt is the square root)

Answer 2

Then you just have to determine which of the two resultant answers give a point that is between A and B.

Let's call two resultants I1 and I2. To determine which one is the answer, you need to check directions of A->I1 and A->I2 vectors against A->B, where A is the point that is located inside the circle:

% line: y = mx + b
m = (yB - yA) / (xB - xA);
b = yA - m * xA;

% circle: x^2 + y^2 = r^2
% intersection: x^2 + (mx + b)^2 = r^2
% ...           x^2 + m^2x^2 + b^2 + 2mbx - r^2 = 0
% ...           (1 + m^2)x^2 + 2mbx + (b^2 - r^2) = 0

A = 1 + m^2;
B = 2 * m * b;
C = b^2 - r^2;
sqrtD = sqrt(B^2 - 4*A*C);

xI = (-B+sqrtD) / (2*A);
yI = m * xI + b;

if (abs(atan2(yB - yA, xB - xA)-atan2(yI - yA, xI - xA)) > 1e-5)
    xI = (-B-sqrtD) / (2*A);
    yI = m * xI + b;
end

Remark #1: I didn't check the delta for being negative, since you said one point is inside the circle and the other is outside of it.

Remark #2: You need to cover the special case where A == B.

Remark #3: You need to cover the special case where xA == xB.

Remark #4: You can pick the correct answer with much less cost than finding the slope of two vectors, calculating the absolute variance between them and comparing the result with an epsilon! :)