Homogeneous Coordinates

mediumFREENotationGeometryCV: Introduction to Computer Vision

Implement a conversion between Cartesian coordinates and homogeneous coordinates, a fundamental concept in projective geometry. This conversion is crucial in computer vision for representing and applying projective transformations.

In Cartesian coordinates, a 2D point is represented as $(x, y)$ . In contrast, homogeneous coordinates introduce an additional dimension, representing the same point as $(x, y, 1)$ . This extension enables the use of linear algebra techniques, such as matrix multiplications, to perform projective transformations.

Here are the steps to convert between these coordinate systems:

To convert from Cartesian to homogeneous, append a third coordinate with value $1$ .
To convert from homogeneous to Cartesian, divide the first two coordinates by the third.

\begin{aligned} (x, y) &\rightarrow (x, y, 1) \\ (X, Y, W) &\rightarrow \left(\frac{X}{W}, \frac{Y}{W}\right) \end{aligned}

This technique is widely used in image processing and computer vision applications.

Example

Input

to_cartesian([6, 8, 2])

Output

[3.0, 4.0]

Reasoning

Input: the homogeneous triple $(X, Y, W) = (6, 8, 2)$ . The first two entries are scaled coordinates and $W$ is the scale factor shared by both.
Math: recover the Cartesian point by dividing each of the first two entries by $W$ : $x = \frac{6}{2} = 3$ and $y = \frac{8}{2} = 4$ .
Output: the 2D point [3.0, 4.0]. It has one fewer entry than the input because $W$ is used up by the division. The values are real numbers (written with a decimal part) because they come from a division, and each is rounded to 4 decimal places, which only matters when $W$ does not divide evenly.
Notice that scaling all three entries by the same nonzero factor names the same point: $(12, 16, 4)$ also gives $(3, 4)$ . Going the other way, $(3, 4)$ simply becomes $(3, 4, 1)$ , and dividing by $W = 1$ returns the original point unchanged.

Constraints

For to_homogeneous: input is [x, y], output is [x, y, 1]
For to_cartesian: input is [X, Y, W], output is [X/W, Y/W] rounded to 4 decimals
W is guaranteed to be non-zero

Learn this in

Introduction to Computer VisionCV Study Plan Image Alignment and StitchingCV Study Plan Introduction to 3D Computer Vision3D Computer Vision

More from CV: Introduction to Computer Vision

Sparse Matrix Operations for Imagesmedium Multi-Scale Feature Pyramidhard Implement Prewitt Edge Detectorhard Connected Components Labelinghard K-Means Color Quantizationmedium

Concept primer

Homogeneous Coordinates: Background and Problem-Solving Guide

Background Knowledge

What are Homogeneous Coordinates?

Homogeneous coordinates extend Cartesian coordinates by adding an extra dimension, enabling a unified representation of points, lines, and transformations in projective geometry. In 2D, a Cartesian point $(x, y)$ becomes $(x, y, 1)$ in homogeneous coordinates by appending a weight factor $W = 1$ . The key insight is that homogeneous coordinates are scale-invariant: the points $(x, y, 1)$ , $(2x, 2y, 2)$ , and $(kx, ky, k)$ all represent the same Cartesian point because they reduce to the same ratio when normalized.

Why Use Homogeneous Coordinates?

The primary advantage is that affine and projective transformations (translation, rotation, scaling, perspective projection) can be represented as matrix multiplications. In Cartesian coordinates, translation requires vector addition, which cannot be expressed as a single matrix operation. Homogeneous coordinates unify all these transformations into linear algebra, making them computationally elegant and efficient for computer graphics and computer vision applications. Additionally, homogeneous coordinates naturally represent points at infinity (when $W = 0$ ), which is essential for projective geometry.

Conversion Rules

The conversion between the two systems is straightforward:

Cartesian to Homogeneous: $(x, y) \rightarrow (x, y, 1)$
Homogeneous to Cartesian: $(X, Y, W) \rightarrow (X/W, Y/W)$

The critical detail is that any scalar multiple of a homogeneous coordinate represents the same point, so $(X, Y, W)$ , $(2X, 2Y, 2W)$ , and $(kX, kY, kW)$ are equivalent.

Algorithm/Approach

The solution involves implementing two conversion functions:

Cartesian → Homogeneous: Append a weight of 1 to the 2D point.
Homogeneous → Cartesian: Divide the first two coordinates by the weight coordinate.

The algorithm is deterministic and direct—no iteration or complex logic is required. However, you must handle edge cases, particularly when $W = 0$ (which represents a point at infinity and cannot be converted to Cartesian coordinates).

Step-by-Step Strategy

For Cartesian to Homogeneous Conversion:

Accept a 2D point as input (e.g., a tuple, list, or array with two elements).
Append the weight factor 1 to create a 3-element homogeneous coordinate.
Return the result as a 3-element structure.

For Homogeneous to Cartesian Conversion:

Accept a 3-element homogeneous coordinate as input.
Check if the weight $W$ is zero (or very close to zero due to floating-point precision). If so, handle this as a special case—either raise an exception, return a special value, or skip the conversion.
If $W \neq 0$ , divide the first two coordinates by $W$ to normalize.
Return the resulting 2D Cartesian point.

Implementation Considerations:

Use appropriate data structures (tuples, lists, or NumPy arrays depending on the problem's requirements).
Decide whether to work with floating-point or integer arithmetic based on the problem constraints.
Consider whether you need to validate inputs (e.g., ensuring homogeneous coordinates have exactly three elements).

Common Pitfalls

Division by Zero: The most critical issue is attempting to convert a homogeneous point with $W = 0$ to Cartesian coordinates. Always check for this condition before dividing.
Floating-Point Precision: When checking if $W = 0$ , use a small epsilon tolerance (e.g., $|W| < 10^{-9}$ ) rather than exact equality, as floating-point arithmetic can introduce rounding errors.
Forgetting the Weight Factor: When converting Cartesian to homogeneous, always append 1, not 0 or any other value. The weight 1 is the standard convention.
Confusing Homogeneous Equivalence: Remember that $(X, Y, W)$ and $(kX, kY, kW)$ represent the same point. If your problem requires normalized homogeneous coordinates (where $W = 1$ ), you may need to normalize after operations.
Data Type Mismatches: Ensure your input and output types are consistent with the problem's expectations (e.g., returning lists vs. tuples, or NumPy arrays vs. Python lists).

Time & Space Complexity

Time Complexity: $O(1)$ for both conversions. Each operation involves a constant number of arithmetic operations (appending a value or dividing two numbers), independent of input size.
Space Complexity: $O(1)$ for the conversion operations themselves. If you're storing results in a new data structure, the space depends on how you represent the coordinates, but this is typically negligible (a 2-element or 3-element array).

solution.py

Python 3.13

Test results