 ### Lei Mao

Machine Learning, Artificial Intelligence, Computer Science.

# 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 == 0:
return None
x = x_homo / x_homo

return (x, x)

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 * intersection + line_1 * intersection + line_1,
0) and np.isclose(
line_2 * intersection + line_2 * intersection +
line_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, point_1, 1)
point_2_homo = (point_2, point_2, 1)
if point_1_homo == point_2_homo:
return None
line = np.cross(point_1_homo, point_2_homo)

return (line, line, line)

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

status = np.isclose(line * point + line * point + line, 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