Weekly exercise 9: Finding the intersection of line segments¶

Given two line segments in $ \mathbb{R}^2 $ with endpoint coordinates as

$$ (x^1_1,y^1_1),(x^1_2,y^1_2) \text{ and } (x^2_1,y^2_1),(x^2_2,y^2_2), $$

where superscripts indicate the segment, subscripts indicate beginning and end of the line, find whether the segments intersect, and if so, what is the intersection point.

Method¶

Let intersection be given by $ (x_0,y_0) $, and introduce two more variables $ t_1 $ and $ t_2 $ that equal to the distance from the starting points $ (x^1_1,y^1_1) $ and $ (x^2_1,y^2_1) $ to the intersection point, relative to the corresponding segment lengths. Then we can write the following system of equations

$$ \begin{eqnarray*} (x^1_2 - x^1_1) \cdot t_1 &=& x_0 - x^1_1 \\ (x^2_2 - x^2_1) \cdot t_2 &=& x_0 - x^2_1 \\ (y^1_2 - y^1_1) \cdot t_1 &=& y_0 - y^1_1 \\ (y^2_2 - y^2_1) \cdot t_2 &=& y_0 - y^2_1 \\ \end{eqnarray*} $$

In matrix notation $ Az=b $ where

$$ A= \begin{pmatrix} x^1_2 - x^1_1 & 0 & -1 & 0 \\ 0 & x^2_2 - x^2_1 & -1 & 0 \\ y^1_2 - y^1_1 & 0 & 0 & -1 \\ 0 & y^2_2 - y^2_1 & 0 & -1 \\ \end{pmatrix},\;\; b=\begin{pmatrix} -x^1_1\\ -x^2_1\\ -y^1_1\\ -y^2_1\\ \end{pmatrix},\;\; z=(t_1,t_2,x_0,y_0) $$

After solving the system, we can check $ t_1 $ and $ t_2 $

• If both belong to $ [0,1] $, the intersection point exists and is given by the computed $ (x_0,y_0) $
• Otherwise, it the segments do not intersect

Task¶

Write a function that takes the coordinates of the two line segments as input, and outputs the coordinates of the intersection point, if it exists, and None otherwise.

Write several tests to check that your function works correctly in both cases when lines do and do not intersect.