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:

  • in case $\Delta = 0$ then the line is tangent to the circle and intersects the circle in one single point.
  • in case $\Delta > 0$ then the line intersects the circle in two points.
  • in case $\Delta < 0$ then the line does not intersect the circle at all.

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 >
    ];
}

fuss/mathematics/geometry/intersections/segment_and_circle.txt ยท Last modified: 2017/02/22 18:30 (external edit)

Access website using Tor Access website using i2p


For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.