Intersection of segments

This article deals with the intersection of two segments ($S_A$ and $S_B$) in 3D. Of course, it also works in 2D : simply set the z-value of each point equal to zero. Each segment is defined by two points:

• segment $S_A$ is defined by points $P_1$ and $P_2$
• segment $S_B$ is defined by points $P_3$ and $P_4$
The following illustration shows a configuration of segments:

Check for parallelism

Before calculating an intersection, you must check if the segments are parallel or not. An efficient method for checking parallelism can be found here.
If the segments are parallel, you must check if they are also collinear. Based on the knowledge of parallelism, checking if $P_1$, $P_2$ and $P_3$ are aligned is enough to conclude about colinearity. An efficient method can be found here.
If the segments are collinear, an intersection may exist. This intersection may be a point or a segment. Let’s compute the following dot products:

$\begin{array}{r c l} K_2=\vec{P_1P_2} \cdot \vec{P_1P_2} \\ K_3=\vec{P_1P_2} \cdot \vec{P_1P_3} \\ K_4=\vec{P_1P_2} \cdot \vec{P_1P_4}\end{array}$
The following table shows all the possibilities of intersection between the segments according to $K_2$, $K_3$ and $K_4$. There is no intersection in the red cells. In the grey cells the intersection is a point and in the blue cells the intersection is a segment. Note that in the middle cell, there is two possibilities that makes necessary to check if $P_3=P_4$ before concluding.

• The segments do not intersect (white cells).
• The intersection is a point (grey cells).
• The intersection is a segment (blue cells)
• 3D case

If the problem statement is expressed in 3D, it is first necessary to check if the lines segments are coplanar i.e. the four points $P_1$, $P_2$, $P_3$ and $P_4$ belong to the same plane. An efficient method can be found here. If the segments are not coplanar, there is no intersection.

Parametric form

The segments can be rewritten in there parametric form :

$\begin{array}{r c l}X_A(t)=P_A + t.\vec{v_A} \\X_B(t)=P_B + t.\vec{v_B}\end{array}$

with:

$\begin{array}{l c l}P_A=P_1 \\P_B=P_3 \\\vec{v_A} = \vec{P_1P_2} \\\vec{v_B} = \vec{P_3P_4} \\0 \le t \le 1\end{array}$

$\vec{P1P3} \cdot (\vec{V_A} \times \vec{V_B}) = 0$

Intersection point

From here we assume that the segments are coplanar and not parallel, therefore the lines passing through $P_1$ and $P_2$ and the line passing through $P_3$ and $P_4$ intersect. The lines intersection must perforce be a point, but this point does not necessarily lie on both segments $S_A$ and $S_B$. If we assume that the lines intersect, we can look for the intersection point $P_i$ that satisfies the two following equations :

$\begin{array}{r c l}P_i=P_A + K_A.\vec{v_A} \\P_i=P_B + K_B.\vec{v_B}\end{array}$

This gives us this equation to solve:

$P_A + K_A.\vec{v_A} = P_B + K_B.\vec{v_B}$

Rewrite the equation:

$K_A.\vec{v_A} = (P_B-P_A) + K_B.\vec{v_B}$

Take the cross product of each side with $\vec{v_B}$:

$K_A.(\vec{v_A} \times \vec{v_B} ) = \vec{P_AP_B} \times \vec{v_B} + K_B.\vec{v_B} \times \vec{v_B}$

Simplify the equation:

$K_A.(\vec{v_A} \times \vec{v_B} ) = \vec{P_AP_B} \times \vec{v_B}$

Take the dot product of each side with $(\vec{v_A} \times \vec{v_B} )$

$K_A.(\vec{v_A} \times \vec{v_B} ) \cdot (\vec{v_A} \times \vec{v_B} ) = (\vec{P_AP_B} \times \vec{v_B}) \cdot (\vec{v_A} \times \vec{v_B} )$

Now deduce $K_A$ and $K_B$:

$K_A= \frac { (\vec{P_AP_B} \times \vec{v_B}) \cdot (\vec{v_A} \times \vec{v_B} ) } { (\vec{v_A} \times \vec{v_B} ) \cdot (\vec{v_A} \times \vec{v_B} ) }=\frac { (\vec{P_1P_3} \times \vec{P_3P_4}) \cdot (\vec{P_1P_2} \times \vec{P_3P_4} ) } { (\vec{P_1P_2} \times \vec{P_3P_4} ) \cdot (\vec{P_1P_2} \times \vec{P_3P_4} ) }$
$K_B= \frac { (\vec{P_BP_A} \times \vec{v_A}) \cdot (\vec{v_B} \times \vec{v_A} ) } { (\vec{v_B} \times \vec{v_A} ) \cdot (\vec{v_B} \times \vec{v_A} ) }=\frac { (\vec{P_1P_3} \times \vec{P_1P_2}) \cdot (\vec{P_1P_2} \times \vec{P_3P_4} ) } { (\vec{P_1P_2} \times \vec{P_3P_4} ) \cdot (\vec{P_1P_2} \times \vec{P_3P_4} ) }$

Note that $\vec{v_A} \times \vec{v_B}$ must not be equal to zero. It happens when the vectors $\vec{v_A}$ and $\vec{v_B}$ are parallel and parallelism must be check prior to calculating $K_A$ and $K_B$. The segments intersect if $0 \le K_A \le 1$ and $0 \le K_B \le 1$:

• $P_i$ lies on segment $S_A$ if $0 \le K_A \le 1$.
• $P_i$ lies on segment $S_B$ if $0 \le K_B \le 1$.

If $K_A \in [0;1]$ and $K_B \in [0;1]$ the intersection point belongs on both segments. The coordinates of the intersection point $P_i$ can easily be calculated with the following formula:

$P_i=P_A+K_A.\vec{v_A} = P_B+K_B.\vec{v_B}$

This is also equal to:

$P_i=P_1+K_A.\vec{P_1P_2} = P_2+K_B.\vec{P_3P_4}$