Algorithm for getting the point where line cuts the circle 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. 

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.
