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