Intersection Between Two Segments Given Four Points


\begin{tikzpicture}

  % grid
  \draw[help lines] (-2,-2) grid (2,2);
  
  % origin
  \draw[black, line width=.1mm] (-0.1,-0.1) -- (0.1,0.1)
    (0.1,-0.1) -- (-0.1,0.1);
  \coordinate[label={[black]below left:$O$}] (O) at (0,0);
  
  \coordinate[label={[cyan]above left:$A$}] (A) at (-2,0);
  \drawpoint{A}{.5mm}{cyan}
  \coordinate[label={[blue]above left:$B$}] (B) at (2,1);
  \drawpoint{B}{.5mm}{blue}
  \coordinate[label={[green]above left:$C$}] (C) at (-1,1);
  \drawpoint{C}{.5mm}{green}
  \coordinate[label={[brown]above right:$D$}] (D) at (2,-1);
  \drawpoint{D}{.5mm}{brown}
  
  \draw (A) -- (B);
  \draw (C) -- (D);
  
  % median for A
  \path[draw, black, line width=.1mm, solid, name path=median from A] (A) -- (B);
  % median for B
  \path[draw, black, line width=.1mm, solid, name path=median from C] (C) -- (D);
  
  % gravity centre
  \path[draw, red, name intersections={of=median from A and median from C, by=I}];
  \drawpoint{I}{.5mm}{red}
  \coordinate[label={[red]above:$I$}] (I) at (I);
  
  %\coordinate (C) at (2,0);
  %\coordinate (D) at (0,1);
  
  %\draw[dotted,->] (O) --  (C) node[below] {$x$};
  %\draw[dotted,->] (O) --  (D) node[left] {$y$};
  
  %\markangle{A}{B}{C}{3mm}{3mm}{$\alpha$}{cyan}{north}
  
\end{tikzpicture}

Given four points with known coordinates:

\begin{eqnarray*}
{\color{cyan}A} &=& A({\color{cyan}a_{1}}, {\color{cyan}a_{2}}, {\color{cyan}a_{3}}) \\
{\color{blue}B} &=& B({\color{blue}b_{1}}, {\color{blue}b_{2}}, {\color{blue}b_{3}}) \\
{\color{green}C} &=& C({\color{green}c_{1}}, {\color{green}c_{2}}, {\color{green}c_{3}}) \\
{\color{brown}D} &=& D({\color{brown}d_{1}}, {\color{brown}d_{2}}, {\color{brown}d_{3}})  
\end{eqnarray*}

Writing the parametric equation for the line $\overline{AB}$:

\begin{eqnarray*}
{\color{cyan}A} + t({\color{blue}B}-{\color{cyan}A}) &=& \begin{pmatrix} 
{\color{cyan}a_{1}} \\
{\color{cyan}a_{2}} \\
{\color{cyan}a_{3}} 
\end{pmatrix} + t\begin{pmatrix} 
{\color{blue}b_{1}} - {\color{cyan}a_{1}} \\
{\color{blue}b_{2}} - {\color{cyan}a_{2}} \\
{\color{blue}b_{3}} - {\color{cyan}a_{3}}
\end{pmatrix}
\end{eqnarray*}

and the parametric equation for the line $\overline{CD}$:

\begin{eqnarray*}
{\color{green}C} + t({\color{brown}D}-{\color{green}C}) &=& \begin{pmatrix} 
{\color{green}c_{1}} \\
{\color{green}c_{2}} \\
{\color{green}c_{3}} 
\end{pmatrix} + s\begin{pmatrix} 
{\color{brown}d_{1}} - {\color{green}c_{1}} \\
{\color{brown}d_{2}} - {\color{green}c_{2}} \\
{\color{brown}d_{3}} - {\color{green}c_{3}}
\end{pmatrix}
\end{eqnarray*}

with $t\in\Re$ and $s\in\Re$. Notice that if $s=0$ then we get the starting point of line $\overline{AB}$ and if $s=1$ then we get the ending point of line $\overline{AB}$. Symmetrically, the same applies to $t=0$, giving the start point of segment $\overline{CD}$ and $t=1$, giving the end point of segment $\overline{CD}$.

Equating the two equations for lines $\overline{AB}$ and $\overline{CD}$, we obtain the system of linear equations:

\begin{eqnarray*}
{\color{cyan}a_{1}} + t({\color{blue}b_{1}}-{\color{cyan}a_{1}}) &=& {\color{green}c_{1}} + s({\color{brown}d_{1}}-{\color{green}c_{1}}) \\
{\color{cyan}a_{2}} + t({\color{blue}b_{2}}-{\color{cyan}a_{2}}) &=& {\color{green}c_{2}} + s({\color{brown}d_{2}}-{\color{green}c_{2}}) \\
{\color{cyan}a_{3}} + t({\color{blue}b_{3}}-{\color{cyan}a_{3}}) &=& {\color{green}c_{3}} + s({\color{brown}d_{3}}-{\color{green}c_{3}}) \\
\end{eqnarray*}

We determine $s$ and $t$ from the first two equations:

\begin{eqnarray*}
t &=& \frac{({\color{brown}d_{1}}-{\color{green}c_{1}})({\color{brown}d_{2}}-{\color{green}c_{2}})-({\color{brown}d_{2}}-{\color{green}c_{2}})({\color{cyan}a_{1}}-{\color{green}c_{1}})}{({\color{brown}d_{2}}-{\color{green}c_{2}})({\color{blue}b_{1}}-{\color{cyan}a_{1}})-({\color{brown}d_{1}}-{\color{green}c_{1}})({\color{blue}b_{2}}-{\color{cyan}a_{2}})} \\
s &=& \frac{({\color{blue}b_{1}}-{\color{cyan}a_{1}})({\color{cyan}a_{2}}-{\color{green}c_{2}})-({\color{blue}b_{2}}-{\color{cyan}a_{2}})({\color{cyan}a_{1}}-{\color{green}c_{1}})}{({\color{brown}d_{2}}-{\color{green}c_{2}})({\color{blue}b_{1}}-{\color{cyan}a_{1}})-({\color{brown}d_{1}}-{\color{green}c_{1}})({\color{blue}b_{2}}-{\color{cyan}a_{2}})}
\end{eqnarray*}

Note that the denominator, call it $\delta$:

\begin{eqnarray*}
\delta &=& ({\color{brown}d_{2}}-{\color{green}c_{2}})({\color{blue}b_{1}}-{\color{cyan}a_{1}})-({\color{brown}d_{1}}-{\color{green}c_{1}})({\color{blue}b_{2}}-{\color{cyan}a_{2}})
\end{eqnarray*}

is the same for both $t$ and $s$.

Judging on cases, we can say that:

  • if $\delta=0$ then the segments do not intersect,
  • if $0\le s, t \le1$ and the third equation is satisfied by $t$ and $s$, then the lines intersect at the point ${\color{red}I}(x, y, z)$, with the coordinates:

\begin{eqnarray*}
x &=& {\color{cyan}a_{1}} + s({\color{cyan}a_{2}} - {\color{cyan}a_{1}}) \\
y &=& {\color{blue}b_{1}} + s({\color{blue}b_{2}} - {\color{blue}b_{1}}) \\
z &=& {\color{green}c_{1}} + s({\color{green}c_{2}} - {\color{green}c_{1}})
\end{eqnarray*}

Implementation

The vectors A, B, C and D are given in parametric form, for example:

vector A = <34.517483, 231.703461, 21.108919>;
vector B = <34.517483, 222.014297, 21.108919>; 
vector C = <29.423143, 226.800842, 21.108919>;
vector D = <38.186848, 226.800842, 21.108919>;

In order to determine whether the segments $\overline{AB}$ and $\overline{CD}$ intersect, one would call the function as:

if(wasSegmentIntersect(A, B, C, D) == TRUE) {
    llOwnerSay("Segments AB and CD intersect.");
    return;
}
llOwnerSay("Segments AB and CD do not intersect.");

wasSegmentIntersect is defined as:

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2014 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
// determines whether the segment AB intersects the segment CD
integer wasSegmentIntersect(vector A, vector B, vector C, vector D) {
    vector s1 = <B.x - A.x, B.y - A.y, B.z - A.z>;
    vector s2 = <D.x - C.x, D.y - C.y, D.y - C.z>;
 
    float d = (s1.x * s2.y -s2.x * s1.y);
 
    if(d == 0) return FALSE;
 
    float s = (s1.x * (A.y - C.y) - s1.y * (A.x - C.x)) / d;
    float t = (s2.x * (A.y - C.y) - s2.y * (A.x - C.x)) / d;
 
    // intersection at <A.x + (t * s1.x), A.y + (t * s1.y), A.z + (t * s1.z)>;
    return (integer)(s >= 0 && s <= 1 && t >= 0 && t <= 1 && 
            A.z + t*(B.z - A.z) == C.z + s*(D.z - C.z));
}

fuss/mathematics/geometry/intersections/two_segments.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.