geometry | Developer notes

In this note I will explain how to find the intersection point P between two line segments. Note that this method will also calculate intersections on extended line segments.

As a reminder the cross product is the area of the parallelogram enclosed by the two As a reminder, the cross product is the area of the parallelogram enclosed by the two vectors. In 2D graphics, we will calculate only the z-component of the cross-vector, which will be called the cross-product in this note.

It can be calculated using the following formula:

$a\times b = a_x b_y - a_y b_x$

Calculating the actual intersection:

As an example we will calculate the intersection point $P$ of line segments $AB$ and $CD$ as shown in image 1.

Image 1

We will consider the line segments as vectors, this gives us the following vectors.

$AB =\begin{pmatrix}6\\3\end{pmatrix}$ , $CD =\begin{pmatrix}-4\\4\end{pmatrix}$

To calculate the intersection point we will first calculate the area of the parallelogram formed by AB and CD as shown in image 2.

Image 2

The area can be calculated using the cross product of $AB \times CD$

$AB\times CD = \begin{pmatrix}6\\3\end{pmatrix}\times\begin{pmatrix}-4\\4\end{pmatrix} = (6.4)-(-4.3) = 24-(-12) = 36$

Calculating the offset on segment $CD$

We will now calculate the area below vector $AB$ as seen in image 3

Image 3

It can be seen the offset on segment on $CD$ will be equal to this area divided by the total area calculated earlier. Fortunately we can easily calculate the area by using the area shown in image 4.

Image 4

The areas shown in image 3 and image 4 are the same. Note that image 4 shows the parallelogram formed by $AC$ and $AB$ , we will use the cross-product to calculate it.

We will introduce vector $AC$ for this.

$AC =\begin{pmatrix}7-2\\3-2\end{pmatrix} = \begin{pmatrix}5\\1\end{pmatrix}$

$AC\times AB = \begin{pmatrix}5\\1\end{pmatrix}\times\begin{pmatrix}6\\3\end{pmatrix} = (5.3)-(1.6) = 15-6 = 9$

Now we are almost done. We have both areas (9 and 36) so we can create the offset

$offset = \frac{9}{36}CD$ which can be simplified to $offset = \frac{1}{4}$

If we multiply the offset with $CD$ we find the point on the vector $CD$ .

Since the line segment $CD$ does not start on $\begin{pmatrix}0\\0\end{pmatrix}$ the actual point needs to be moved by $C$

$P = C + \frac{1}{4}CD$

Let’s check whether it is correct

$P = C + \frac{1}{4}CD = \begin{pmatrix}7\\3\end{pmatrix} + \begin{pmatrix} \frac{1}{4}(-4)\\ \frac{1}{4}4\end{pmatrix} = \begin{pmatrix}6\\4\end{pmatrix}$

As a general formula:

$\boxed{P = C + \frac{AC\times AB}{AB \times CD}CD}$

The offset on $CD$ can be negative or larger then one. In that case the intersection is on the extension of line segment $CD$ . This is an advantage of this method.

Calculating the offset on segment $AB$

For the offset of $P$ on $AB$ we repeat the steps above.

We know calculate the area as shown at image 5

Image 5

Which equals the area shown in image 6.

Image 6

$AC\times CD = \begin{pmatrix}5\\1\end{pmatrix}\times\begin{pmatrix}-4\\4\end{pmatrix} = (5.4)-(1.-4) = 20-(-4) =24$

$P = A + \frac{24}{36}AB \to P = A + \frac{2}{3}AB$

Let’s check whether it is correct

$P = A + \frac{2}{3}AB = \begin{pmatrix}2\\2\end{pmatrix} + \begin{pmatrix} \frac{2}{3}(6)\\ \frac{2}{3}3\end{pmatrix} = \begin{pmatrix}6\\4\end{pmatrix}$

As a general formula:

$\boxed{P = A + \frac{AC\times CD}{AB \times CD}AB}$

Developer notes

Stuff I need to remember

Tag Archives: geometry

2D Line intersection using vectors