Table of Contents

Intersection Between a Segment and a Circle

\begin{tikzpicture} % grid \draw[help lines] (-2,-2) grid (2,2); % origin \draw[red, line width=.1mm] (-0.1,-0.1) -- (0.1,0.1) (0.1,-0.1) -- (-0.1,0.1); \coordinate[label={[red]above left:$O(x_{0}, y_{0})$}] (O) at (0,0); \coordinate (R) at (2,0); % coord \coordinate[label={[green]above left:$P_{1}(x_{1},y_{1})$}] (A) at (0,2); \drawpoint{A}{.5mm}{black} \coordinate[label={[blue]above right:$P_{2}(x_{2},y_{2})$}] (B) at (1.7,1); \drawpoint{B}{.5mm}{black} % lines \draw (A) -- (B); %radius \draw[fill=orange,fill opacity=0.1] (O) -- (R); %circle \draw [black] (0,0) circle [radius=2]; %brace \drawbrace{O}{R}{2mm}{orange}{$r$}{0}{-4mm}{mirror}; \end{tikzpicture}

We know that the circle equation is:

\begin{eqnarray*} (x-{\color{red}x_{0}})^{2}+(y-{\color{red}y_{0}})^{2} &=& {\color{orange}r}^{2} \end{eqnarray*}

we also know that the equations for a segment $\overline{P_{1}P_{2}}$ passing through two points $P_{1}=({\color{green}x_{1}}, {\color{green}y_{1}})$ and $P_{2}=({\color{blue}x_{2}},{\color{blue}y_{2}})$ is:

\begin{eqnarray*} x(t) &=& {\color{green}x_{1}} + ({\color{blue}x_{2}}-{\color{green}x_{1}}) * t \\ y(t) &=& {\color{green}y_{1}} + ({\color{blue}y_{2}}-{\color{green}y_{1}}) * t \end{eqnarray*}

knowing that $t:\Re \mapsto [0,1]$, or, in other words, $0 \le t \le 1$.

We substitute $y$ for $y(t)$ and $x$ for $x(t)$ in the circle equation and obtain:

\begin{eqnarray*} ({\color{green}x_{1}} + ({\color{blue}x_{2}}-{\color{green}x_{1}}) * t-{\color{red}x_{0}})^{2}+({\color{green}y_{1}} + ({\color{blue}y_{2}}-{\color{green}y_{1}}) * t-{\color{red}y_{0}})^{2} &=& {\color{orange}r}^{2} \end{eqnarray*}

Now, we want to collect $t$, so we expand the left hand side and obtain:

\begin{eqnarray*} {\color{red}x_{0}}^{2} - 2 {\color{red}x_{0}} {\color{green}x_{1}} + 2 t {\color{red}x_{0}} {\color{green}x_{1}} + {\color{green}x_{1}}^{2} - 2 t {\color{green}x_{1}}^{2} + t^{2} {\color{green}x_{1}}^{2} - \\ 2 t {\color{red}x_{0}} {\color{blue}x_{2}} + 2 t {\color{green}x_{1}} {\color{blue}x_{2}} - 2 t^{2} {\color{green}x_{1}} {\color{blue}x_{2}} + t^{2} {\color{blue}x_{2}}^{2} + {\color{red}y_{0}}^{2} - \\ 2 {\color{red}y_{0}} {\color{green}y_{1}} + 2 t {\color{red}y_{0}} {\color{green}y_{1}} + {\color{green}y_{1}}^{2} - 2 t {\color{green}y_{1}}^{2} + t^{2} {\color{green}y_{1}}^{2} - 2 t {\color{red}y_{0}} {\color{blue}y_{2}} + \\ 2 t {\color{green}y_{1}} {\color{blue}y_{2}} - 2 t^{2} {\color{green}y_{1}} {\color{blue}y_{2}} + t^{2} {\color{blue}y_{2}}^{2} &=& {\color{orange}r}^{2} \end{eqnarray*}

and collect $t$:

\begin{eqnarray*} t^{2} ({\color{green}x_{1}}^{2} - 2 {\color{green}x_{1}} {\color{blue}x_{2}} + {\color{blue}x_{2}}^{2} + {\color{green}y_{1}}^{2} - 2 {\color{green}y_{1}} {\color{blue}y_{2}} + {\color{blue}y_{2}}^{2}) + \\ t (2 {\color{red}x_{0}} {\color{green}x_{1}} - 2 {\color{green}x_{1}}^{2} - 2 {\color{red}x_{0}} {\color{blue}x_{2}} + 2 {\color{green}x_{1}} {\color{blue}x_{2}} + 2 {\color{red}y_{0}} {\color{green}y_{1}} - 2 {\color{green}y_{1}}^{2} - 2 {\color{red}y_{0}} {\color{blue}y_{2}} + 2 {\color{green}y_{1}} {\color{blue}y_{2}}) + \\ {\color{red}x_{0}}^2 - 2 {\color{red}x_{0}} {\color{green}x_{1}} + {\color{green}x_{1}}^2 + {\color{red}y_{0}}^2 - 2 {\color{red}y_{0}} {\color{green}y_{1}} + {\color{green}y_{1}}^2 &=& {\color{orange}r}^{2} \end{eqnarray*}

Passing ${\color{orange}r}^{2}$ from the right-hand side to the left-hand side, we can rewrite the equation as:

\begin{eqnarray*} t^{2} ({\color{green}x_{1}}^{2} - 2 {\color{green}x_{1}} {\color{blue}x_{2}} + {\color{blue}x_{2}}^{2} + {\color{green}y_{1}}^{2} - 2 {\color{green}y_{1}} {\color{blue}y_{2}} + {\color{blue}y_{2}}^{2}) + \\ t (2 {\color{red}x_{0}} {\color{green}x_{1}} - 2 {\color{green}x_{1}}^{2} - 2 {\color{red}x_{0}} {\color{blue}x_{2}} + 2 {\color{green}x_{1}} {\color{blue}x_{2}} + 2 {\color{red}y_{0}} {\color{green}y_{1}} - 2 {\color{green}y_{1}}^{2} - 2 {\color{red}y_{0}} {\color{blue}y_{2}} + 2 {\color{green}y_{1}} {\color{blue}y_{2}}) + \\ ({\color{red}x_{0}}^2 - 2 {\color{red}x_{0}} {\color{green}x_{1}} + {\color{green}x_{1}}^2 + {\color{red}y_{0}}^2 - 2 {\color{red}y_{0}} {\color{green}y_{1}} + {\color{green}y_{1}}^2) - {\color{orange}r}^{2} &=& 0 \end{eqnarray*}

We can observe that if we name the bracketed expressions in the equation above $a$, $b$ respectively $c$:

\begin{eqnarray*} a &=& ({\color{green}x_{1}}^{2} - 2 {\color{green}x_{1}} {\color{blue}x_{2}} + {\color{blue}x_{2}}^{2} + {\color{green}y_{1}}^{2} - 2 {\color{green}y_{1}} {\color{blue}y_{2}} + {\color{blue}y_{2}}^{2}) \\ b &=& (2 {\color{red}x_{0}} {\color{green}x_{1}} - 2 {\color{green}x_{1}}^{2} - 2 {\color{red}x_{0}} {\color{blue}x_{2}} + 2 {\color{green}x_{1}} {\color{blue}x_{2}} + 2 {\color{red}y_{0}} {\color{green}y_{1}} - 2 {\color{green}y_{1}}^{2} - 2 {\color{red}y_{0}} {\color{blue}y_{2}} + 2 {\color{green}y_{1}} {\color{blue}y_{2}}) \\ c &=& ({\color{red}x_{0}}^2 - 2 {\color{red}x_{0}} {\color{green}x_{1}} + {\color{green}x_{1}}^2 + {\color{red}y_{0}}^2 - 2 {\color{red}y_{0}} {\color{green}y_{1}} + {\color{green}y_{1}}^2) - {\color{orange}r}^{2} \end{eqnarray*}

then we can reduce $a$, $b$ and $c$ to:

\begin{eqnarray*} a &=& ({\color{green}x_{1}} - {\color{blue}x_{2}})^2 + ({\color{green}y_{1}} - {\color{blue}y_{2}})^2 \\ b &=& 2 (({\color{red}x_{0}} - {\color{green}x_{1}}) ({\color{green}x_{1}} - {\color{blue}x_{2}}) + ({\color{red}y_{0}} - {\color{green}y_{1}}) ({\color{green}y_{1}} - {\color{blue}y_{2}})) \\ c &=& ({\color{red}x_{0}} - {\color{green}x_{1}})^2 + ({\color{red}y_{0}} - {\color{green}y_{1}})^2 - {\color{orange}r}^2 \end{eqnarray*}

Looking at the equation now, we have a second-degree equation in $t$ with $a$, $b$ and $c$:

\begin{eqnarray*} at^{2} + bt + c &=& 0 \end{eqnarray*}

The solutions for this equation are:

\begin{eqnarray*} t_{1,2} &=& \frac{-b \pm \sqrt{b^{2}-4ac}}{2a} \end{eqnarray*}

where we know $a$, $b$, $c$.

Now the discriminant is $\Delta = b^{2}-4ac}$ and depending on $\Delta$ we have the cases:

By substituting $t_{1,2}$ in the equation of the segment for $x(t)$ respectively $y(t)$ we obtain the point(s) of intersection between the segment $\overline{P_{1}P_{2}}$ and the circle:

\begin{eqnarray*} P_{1} &=& ({\color{green}x_{1}}, {\color{green}y_{1}}) = ({\color{green}x_{1}}+({\color{blue}x_{2}}-{\color{green}x_{1}})*t_{1}, {\color{green}y_{1}}+({\color{blue}y_{2}}-{\color{green}y_{1}}) * t_{1}) \\ P_{2} &=& ({\color{blue}x_{2}}, {\color{blue}y_{2}}) = ({\color{green}x_{1}}+({\color{blue}x_{2}}-{\color{green}x_{1}})*t_{2}, {\color{green}y_{1}}+({\color{blue}y_{2}}-{\color{green}y_{1}}) * t_{2}) \end{eqnarray*}

where we know $t_{1,2}$ from the expression above.

Implementation

The reason for simplifying $a$, $b$ and $c$, keeping $\Delta$ as an relation between $a$, $b$ and $c$ and by working symbolically we can reduce the number of operations that an implementation may have to do.

LSL

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2014 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
// given a circle with centre in C(x0x, c0y) and radius r and two points
// p1 and p2 defining a line, the function returns the empty list if the
// line p1p2 does not intersect the circle or a list containing two vectors
// of the the intersection point(s).
list wasLineIntersectCircle(float c0x, float c0y, float r, vector p1, vector p2) {
    // let dx = p1.x-p2.x
    // let dy = p1.y-p2.y
    float dx = p1.x - p2.x;
    float dy = p1.y - p2.y;
 
    // let dcx = c0x-p1.x
    // let dcy = c0y-p1.y
    float dcx = c0x - p1.x;
    float dcy = c0y - p1.y;
 
    float a = llPow(dx, 2) + llPow(dy, 2);
    float b = 2 * (dcx * dx + dcy * dy);
    float c = llPow(dcx, 2) + llPow(dcy, 2) - llPow(r, 2);
 
    // delta
    float delta = llPow(b, 2) - 4 * a * c;
 
    if (delta < 0) {
        // no intersection, no points
        return [];
    }
 
    float t1 = (-b + llSqrt(delta)) / (2 * a);
    float t2 = (-b - llSqrt(delta)) / (2 * a);
 
    return [
        < p1.x - dx * t1, p1.y - dy * t1, 0 >,
        < p1.x - dx * t2, p1.y - dy * t2, 0 >
    ];
}