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$.

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

Homogeneous Coordinates

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

$$\begin{array}{rl}\tilde{\mathbf{x}}& =\tilde{w}\overline{\mathbf{x}}\\ & =\tilde{w}(x,y,1)\\ & =(\tilde{w}x,\tilde{w}y,\tilde{w})\\ & =(\tilde{x},\tilde{y},\tilde{w})\end{array}$$

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 $\Vert \mathbf{n}\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{array}{c}\overline{\mathbf{x}}\cdot {\tilde{\mathbf{l}}}_1=0\\ \overline{\mathbf{x}}\cdot {\tilde{\mathbf{l}}}_2=0\end{array}$$

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{array}{c}({\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{array}$$

We must have

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

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

Therefore,

$$\begin{array}{rl}\overline{\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{array}$$

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{array}{c}{\overline{\mathbf{x}}}_1\cdot \tilde{\mathbf{l}}=0\\ {\overline{\mathbf{x}}}_2\cdot \tilde{\mathbf{l}}=0\end{array}$$

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

$$\begin{array}{c}{\overline{\mathbf{x}}}_1\cdot ({\overline{\mathbf{x}}}_1\times {\overline{\mathbf{x}}}_2)=0\\ {\overline{\mathbf{x}}}_2\cdot ({\overline{\mathbf{x}}}_1\times {\overline{\mathbf{x}}}_2)=0\end{array}$$

We must have

$$\begin{array}{rl}{\overline{\mathbf{x}}}_1\times {\overline{\mathbf{x}}}_2& =\tilde{v}\overline{\mathbf{l}}\\ & =\tilde{\mathbf{l}}\end{array}$$

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

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

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