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:

Overview

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.

TableCollinear

  • The segments do not intersect (white cells).
  • CollinearCase1

  • The intersection is a point (grey cells).
  • CollinearCase2

  • The intersection is a segment (blue cells)
  • CollinearCase3

    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

    Vectors

    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}

    Leave a Reply

    Your email address will not be published. Required fields are marked *