2D Line Mathematics Using Homogeneous Coordinates

Introduction

It is possible to compute the intersection of two lines and the line given two points using cross-product.

In this blog post, I would like to quickly derive how to do so using homogeneous coordinate representations.

2D Point Representations

Inhomogeneous Coordinates

The inhomogeneous coordinates for a 2D point are just ordinary two-value Cartesian coordinates.

$$
\mathbf{x} = (x, y)
$$

Augmented Coordinates

The augmented coordinates for a 2D point are just the 2D inhomogeneous coordinates with an additional constant $1$.

$$
\bar{\mathbf{x}} = (x, y, 1)
$$

Homogeneous Coordinates

The homogeneous coordinates are just the augmented coordinates scaled by some value $\tilde{w}$.

$$
\begin{align}
\tilde{\mathbf{x}} &= \tilde{w} \bar{\mathbf{x}} \\
&= \tilde{w} (x, y, 1) \\
&= (\tilde{w}x, \tilde{w}y, \tilde{w}) \\
&= (\tilde{x}, \tilde{y}, \tilde{w}) \\
\end{align}
$$

where $\tilde{w} \in \mathbb{R}$.

When $\tilde{w} = 0$, $\tilde{\mathbf{x}}$ is called ideal point and do not have the corresponding inhomogeneous coordinates.

Intersection

The 2D line $l: ax + by + c = 0$ could be represented using homogeneous coordinates, $\tilde{\mathbf{l}} = (a, b, c)$. It can also be normalized so that $\mathbf{l} = (\hat{n}_x, \hat{n}_y, d) = (\mathbf{n}, d)$ with $\left\Vert \mathbf{n} \right\Vert = 1$.

Suppose $\mathbf{x} = (x, y)$ is the intersection of two lines $\tilde{\mathbf{l}}_1 = (a_1, b_1, c_1)$ and $\tilde{\mathbf{l}}_2 = (a_2, b_2, c_2)$, we must have

$$
\begin{gather}
\bar{\mathbf{x}} \cdot \tilde{\mathbf{l}}_1 = 0 \\
\bar{\mathbf{x}} \cdot \tilde{\mathbf{l}}_2 = 0 \\
\end{gather}
$$

Because the cross product of $\tilde{\mathbf{l}}_1$ and $\tilde{\mathbf{l}}_2$, $\tilde{\mathbf{l}}_1 \times \tilde{\mathbf{l}}_2$, is perpendicular to both $\tilde{\mathbf{l}}_1$ and $\tilde{\mathbf{l}}_2$, i.e.,

$$
\begin{gather}
(\tilde{\mathbf{l}}_1 \times \tilde{\mathbf{l}}_2) \cdot \tilde{\mathbf{l}}_1 = 0 \\
(\tilde{\mathbf{l}}_1 \times \tilde{\mathbf{l}}_2) \cdot \tilde{\mathbf{l}}_2 = 0 \\
\end{gather}
$$

We must have

$$
\begin{align}
\tilde{\mathbf{l}}_1 \times \tilde{\mathbf{l}}_2
&= \tilde{w} \bar{\mathbf{x}} \\
&= (\tilde{w}x, \tilde{w}y, \tilde{w}) \\
\end{align}
$$

for some $\tilde{w} \in \mathbb{R}$.

Therefore,

$$
\begin{align}
\bar{\mathbf{x}} =
&= \frac{1}{\tilde{w}} \tilde{\mathbf{l}}_1 \times \tilde{\mathbf{l}}_2 \\
&= \frac{1}{\tilde{w}} (\tilde{w}x, \tilde{w}y, \tilde{w}) \\
\end{align}
$$

line_intersection.py

from typing import Tuple, Optional
import numpy as np


def get_2d_line_intersection(
        line_1: Tuple[float, float, float],
        line_2: Tuple[float, float, float]) -> Optional[Tuple[float, float]]:
    """Get the 2D line intersection.

    Args:
        line_1 (Tuple[float, float, float]): Homogenous coordinate representation of a 2D line.
        line_2 (Tuple[float, float, float]): Homogenous coordinate representation of a 2D line.

    Returns:
        Tuple[float, float]: Inhomogeneous coordinate representation of the intersection.
    """

    x_homo = np.cross(line_1, line_2)
    if x_homo[2] == 0:
        return None
    x = x_homo / x_homo[2]

    return (x[0], x[1])


def verify_2d_line_intersection(line_1: Tuple[float, float, float],
                                line_2: Tuple[float, float, float],
                                intersection: Tuple[float, float]) -> bool:

    status = np.isclose(
        line_1[0] * intersection[0] + line_1[1] * intersection[1] + line_1[2],
        0) and np.isclose(
            line_2[0] * intersection[0] + line_2[1] * intersection[1] +
            line_2[2], 0)

    return status


if __name__ == "__main__":

    np.random.seed(0)

    line_1 = np.random.rand(3)
    line_2 = np.random.rand(3)

    intersection = get_2d_line_intersection(line_1=line_1, line_2=line_2)
    print(intersection)
    if intersection is not None:
        status = verify_2d_line_intersection(line_1=line_1,
                                             line_2=line_2,
                                             intersection=intersection)
        assert status == True

2D Line from 2D Points

Suppose the line $\tilde{\mathbf{l}} = (a, b, c)$ passes two points $\mathbf{x}_1 = (x_1, y_1)$ and $\mathbf{x}_2 = (x_2, y_2)$, similar to the intersection calculation, we must have

$$
\begin{gather}
\bar{\mathbf{x}}_1 \cdot \tilde{\mathbf{l}} = 0 \\
\bar{\mathbf{x}}_2 \cdot \tilde{\mathbf{l}} = 0 \\
\end{gather}
$$

Because the cross product of $\bar{\mathbf{x}}_1$ and $\bar{\mathbf{x}}_2$, $\bar{\mathbf{x}}_1 \times \bar{\mathbf{x}}_2$, is perpendicular to both $\bar{\mathbf{x}}_1$ and $\bar{\mathbf{x}}_2$, i.e.,

$$
\begin{gather}
\bar{\mathbf{x}}_1 \cdot (\bar{\mathbf{x}}_1 \times \bar{\mathbf{x}}_2) = 0 \\
\bar{\mathbf{x}}_2 \cdot (\bar{\mathbf{x}}_1 \times \bar{\mathbf{x}}_2) = 0 \\
\end{gather}
$$

We must have

$$
\begin{align}
\bar{\mathbf{x}}_1 \times \bar{\mathbf{x}}_2
&= \tilde{v} \bar{\mathbf{l}} \\
&= \tilde{\mathbf{l}} \\
\end{align}
$$

If the two points were represented using homogeneous coordinates, equivalently,

$$
\begin{align}
\tilde{\mathbf{x}}_1 \times \tilde{\mathbf{x}}_2
&= \tilde{\mathbf{l}} \\
\end{align}
$$

line_representation.py

from typing import Tuple, Optional
import numpy as np


def get_2d_line(
        point_1: Tuple[float, float],
        point_2: Tuple[float, float]) -> Optional[Tuple[float, float, float]]:
    """Get the 2D line.

    Args:
        point_1 (Tuple[float, float, float]): Inhomogeneous coordinate representation of a 2D point.
        point_2 (Tuple[float, float, float]): Inhomogeneous coordinate representation of a 2D point.

    Returns:
        Tuple[float, float]: Homogeneous coordinate representation of the 2D line.
    """

    point_1_homo = (point_1[0], point_1[1], 1)
    point_2_homo = (point_2[0], point_2[1], 1)
    if point_1_homo == point_2_homo:
        return None
    line = np.cross(point_1_homo, point_2_homo)

    return (line[0], line[1], line[2])


def verify_2d_line_point(line: Tuple[float, float, float],
                         point: Tuple[float, float]) -> bool:

    status = np.isclose(line[0] * point[0] + line[1] * point[1] + line[2], 0)

    return status


if __name__ == "__main__":

    np.random.seed(0)

    point_1 = np.random.rand(2)
    point_2 = np.random.rand(2)

    line = get_2d_line(point_1=point_1, point_2=point_2)
    print(line)
    if line is not None:
        status = verify_2d_line_point(line=line, point=point_1)
        assert status == True
        status = verify_2d_line_point(line=line, point=point_2)
        assert status == True

References

• Cross Product