Algorithm for getting the point where line cuts the circle

Question

I have a circle and a few lines intersecting the circle.

What I know about the problem is:

• The radius (R) of circle.
• The center(C) of circle.
• The start (S) and end (E) of lines.

Using this information, how can I calculate the (green) points on the circle?

I won't be doing this on paper but writing a method in C++. So, I need possibly a pseudocode algorithm which can do this.

Answer 1

In Mathematica:

c = {0, 0};
r = 1;
s = {.5, .2};
ee = {3, 6};
a s + (1 - a) ee  /. 
 Solve[0 < a < 1 && (a s + (1 - a) ee - c).(a s + (1 - a) ee - c) == 
    r^2, a]

Any point on the line segment can be described by $a s + (1 - a) ee$ for $0<a<1$. Solve for that value of $a$ such that the squared distance between the corresponding point and the center $c$ is $r^2$.

Answer 2

If you know the start point and endpoint, then you have a unique line $y = mx + c$.

If you know the circle's center $(a, b)$ and radius $r$, then your circle has equation $(x - a)^2 + (y - b)^2 = r^2$

Plugging the line into the circle will give you a quadratic equation that you can solve for $x$. Once that is done, a direct formula can give you those points.

Answer 3

Define your line segment parametrically:

$$\begin{bmatrix} x \\ y \end{bmatrix} = S + (E-S)t \tag{P1}$$

Note that at $t = 0$, that $\begin{bmatrix} x \\ y \end{bmatrix} = S$, and that at $t = 1$, that $\begin{bmatrix} x \\ y \end{bmatrix} = E$.

Then your circle is given by

$$(x - C_x)^2 + (y - C_y)^2 = r^2$$

Plug the line (P1) in to the circle to find the $t$ value:

$$(S_x + (E_x - S_x)t - C_x)^2 + (S_y + (E_y - S_y)t - C_y)^2 = r^2$$

This is a quadratic equation in $t$:

$$At^2 + Bt + D = 0 \tag{P2}$$

• $A = (S_x - E_x)^2 + (S_y - E_y)^2$
• $B = (S_x - C_x)(E_x - S_x) + (S_y - C_y)(E_y - S_y)$
• $D = (S_x - C_x)^2 + (S_y - C_y)^2 - r^2$

Solve (P2) for $t$ using the quadratic formula. Only the solution (if there is one) with $0 \le t \le 1$ is on the line segment. Plug the found $t$ into (P1) to get the intersection.

Answer 4

Since you mentioned algorithms, you could use a Bresenham style algorithm. Let

$$F(x, y) = (x - C_x)^2 + (y - C_y)^2 - r^2$$

Note that if $F(x, y) > 0$ then $(x, y)$ is outside the circle, and if $F(x, y) < 0$ then $(x, y)$ is inside the circle. Now you can just do a binary search along the line segment, keeping $F(x_1, y_1) < 0$ and $F(x_2, y_2) > 0$ until you have enough precision.

If F(E) < 0 then return "Error, E inside circle"
If F(S) > 0 then return "Error, S outside circle"
V1 = E    
V2 = S    
Loop:
  // assert V1 outside circle
  // assert V2 inside circle
  M = (V1 + V2)/2
  If F(M) = 0              then return (M, M)
  If |V1 - V2| < Precision then return (V1, V2)
  If F(M) < 0 then V2 = M
  If F(M) > 0 then V1 = M

That's one bit of accuracy per loop. If you want it to close in faster, use the value of F to bias M towards which V has less error:

M = (-F(V2) * V1 + F(V1) * V2) / (F(V1) - F(V2))

The advantage of the Bresenham style approach is that you can always guarantee that the answer is between V1 and V2, and guarantees of correctness are always more important than unrequired or unproven speed.