User:KYN/Homogeneous representations in 2D

In a 2-dimensional space, e.g. R², geometrical objects such as points and lines can be given a homogeneous representation in terms of homogeneous coordinates. Also transformations on these objects, e.g., rotations or translations, can be given a homogeneous representation. The reason for introducing a homogeneous representation for points and lines and transformations is that

• A relative large class of transformations can be represented by linear transformation on the homogeneous coordinates, even though the corresponding transformation on the 2D coordinates of, e.g., a point or a line, is not linear. Examples of such transformations are presented below.

• Various geometrical relations, e.g., incidence between a point and a line, can be represented in a simple way. Examples of such relations are presented below.

The usual approach is to first introduce a homogeneous representation for points and all other homogeneous representation, e.g., of lines and various transformations, follows from that. The homogeneous representation for points is usually defined by introducing an additional dimension where the corresponding coordinate assumes a constant value. In the literature on this topic the extra dimension is usually placed either as the first or as the last dimension in the homogeneous representation. The specific value of the constant coordinate in the additional dimension can, in principle, assume any non-zero value. Most literature assign a unit value to this coordinate, but it should be noted that for practical or numerical reasons, it may be desirable to choose another value for this constant.

In this presentation, the extra dimension is placed last and it is given a unit value, which appears to be the most common practice in the literature. It should be noted that every other homogeneous representation of 2D points can be obtained by a suitable linear transformation of the homogeneous coordinates.

Homogeneous representation of 2D points

A 2D point

$x={\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}$

is given a homogeneous representation in the form of the 3D vector $\mathbf {x}$ according to

:$\mathbf {x} ={\begin{pmatrix}x_{1}\\x_{2}\\1\end{pmatrix}}$

The elements of $\mathbf {x}$ are called the homogeneous coordinates of ${\mathit {x}}$

To fully enjoy all the benefits of a homogeneous representation, it is sometimes necessary to see $\mathbf {x}$ as an element of a projective space, i.e., any non-zero scaling of $\mathbf {x}$ is considered as an equivalent representation of the 2D point $x$. This type of equality is here denoted with a $\sim$ sign, which is interpreted as $\mathbf {x} \sim a\mathbf {x}$ for $a\in \mathbb {R} ,a\neq 0$.

A consequence of $\mathbf {x}$ being an element of a projective space is that when it is known, e.g., after being computed from some other known entities, it may be any of the vectors $a\mathbf {x}$ for $a\in \mathbb {R} ,a\neq 0$ that we have at hand. In order to obtain the corresponding vector $x$ we must then first do a proper normalization:

$x={\begin{pmatrix}{\frac {X_{1}}{aX_{3}}}\\[2mm]{\frac {X_{2}}{aX_{3}}}\end{pmatrix}}$

where

$\mathbf {x} ={\begin{pmatrix}X_{1}\\X_{2}\\X_{3}\end{pmatrix}}\sim {\begin{pmatrix}a\,x_{1}\\a\,x_{2}\\a\end{pmatrix}}$

Notice that this transformation from $\mathbf {x}$ to $x$ requires that $X_{3}\neq 0\,$. Any such vector $\mathbf {x}$ is a homogeneous representation of a proper 2D point.

Points at infinity

A useful feature of the homogeneous representation is that it allows points which are at infinite distance from the origin to be represented in a consistent way. Points at infinity have a homogeneous representation as

$\mathbf {x} ={\begin{pmatrix}X_{1}\\X_{2}\\0\end{pmatrix}}$

The transformation from this homogeneous coordinate to a 2D point according to the expression above yields an indefinite vector since we cannot divide by zero. On the other hand, the previous vector can also be seen as the limit value of

$\mathbf {x} ={\begin{pmatrix}X_{1}\\X_{2}\\X_{3}\end{pmatrix}}$

when $X_{3}\rightarrow 0\,$. This can be interpreted in a consistent way as a point which lies at infinite distance from the origin and in the direction defined by the vector

${\begin{pmatrix}X_{1}\\X_{2}\end{pmatrix}}$

The term "direction" is somewhat misleading. Since $\mathbf {x}$ is a projective element

$\mathbf {x} ={\begin{pmatrix}X_{1}\\X_{2}\\0\end{pmatrix}}\sim -{\begin{pmatrix}X_{1}\\X_{2}\\0\end{pmatrix}}={\begin{pmatrix}-X_{1}\\-X_{2}\\0\end{pmatrix}}$

which means that we can find a point at infinity by going in two opposite directions and that the two resulting points in this representation have to be thought of as the same point. Even though this may appear strange from an intuitive point of view, this interpretation of points at infinity is consistent with the geometrical statements which sometimes produce such homogeneous representations. Examples of this are presented below.

The zero vector

The above transformations from homogeneous coordinates back to either a "proper" 2D point or a point at infinity applies to all 3D vectors $\mathbf {x}$ except for $\mathbf {x} =\mathbf {0}$. However, this last case will sometimes be the results of various operations on homogeneous coordinates, so we need an interpretation also for the zero vector. The most natural interpretation is that the zero vector is an "exception flag" which indicates either that there is no answer for some particular computation or it is ambiguous.

The same discussion applies to any type of zero vector, matrix or tensor which may appear as homogeneous representations of various types of geometrical objects. Projective elements which are zero flag exceptions.

Equality of 2D points

Given two vectors in 2D

$x={\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}\quad y={\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}$

they are equal, i.e., referring to the same point when $x=y$, or, $x-y=0$. When these points are given in terms of homogeneous coordinates $\mathbf {x}$ and $\mathbf {y}$ it is no longer true that $\mathbf {x} -\mathbf {y} =0$ when the points are identical. The reason is that there is an arbitrary non-zero scaling on each of the two vectors and only after proper normalization can the subtraction be mande to see if the result is zero. As an alternative to this normalization, if follows directly that if $\mathbf {x}$ and $\mathbf {y}$ both are non-zero, then they represent the same 2D point if and only if

$\mathbf {x} \times \mathbf {y} =\mathbf {0}$

This operation is often a simpler way to check equality when we are dealing with homogeneous coordinates.

Homogeneous representation of 2D lines

Any 2D line can be described as the set of points

$x={\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}$

which satisfies the condition

$x_{1}\,l_{1}+x_{2}\,l_{2}=l\,$

where $l_{1}^{2}+l_{2}^{2}=1$ and $l\geq 0$. This particular type of parametrization of a line is chosen since it allows any slope of the line to be described. In fact, $l_{1}$ and $l_{2}$ represent the cosine and sine of the slope angle $\theta$ and $l$ is the shortest distance from the line to the origin.

The above equation which characterizes a line can be rewritten as

${\begin{pmatrix}x_{1}\\x_{2}\\1\end{pmatrix}}\cdot {\begin{pmatrix}l_{1}\\l_{2}\\-l\end{pmatrix}}=\mathbf {x} \cdot {\begin{pmatrix}l_{1}\\l_{2}\\-l\end{pmatrix}}=0$

From this expression, it can be seen that if we use the 3D vector

:$\mathbf {l} ={\begin{pmatrix}l_{1}\\l_{2}\\-l\end{pmatrix}}$

as a homogeneous representation of the line, it then follows that

the point represented by $\mathbf {x}$ lies on the line represented by $\mathbf {l}$   is equivalent to   $\mathbf {x} \cdot \mathbf {l} =0$

Having defined $\mathbf {l}$ in this way it should be clear that it, too, can be characterized as a projective element since a non-zero scaling of $\mathbf {l}$ does not change the above statement about the point and the line. In this case, the vector $\mathbf {l}$ includes a scale factor which needs to be taken care of in order to recover the parameters of the line. From the relation

$\mathbf {l} ={\begin{pmatrix}L_{1}\\L_{2}\\L_{3}\end{pmatrix}}\sim {1 \over {\sqrt {L_{1}^{2}+L_{2}^{2}}}}{\begin{pmatrix}L_{1}\\L_{2}\\L_{3}\end{pmatrix}}$

if follows that

$l={-L_{3} \over {\sqrt {L_{1}^{2}+L_{2}^{2}}}},l_{1}={L_{1} \over {\sqrt {L_{1}^{2}+L_{2}^{2}}}},l_{2}={L_{2} \over {\sqrt {L_{1}^{2}+L_{2}^{2}}}}$

Notice that this transformation from $\mathbf {l}$ to the parameters of the line requires that ${\sqrt {L_{1}^{2}+L_{2}^{2}}}\neq 0$. Any such homogeneous coordinate represents a proper 2D line.

To distinguish the homogeneous representation of a point from that of a line, the latter type is in the following referred to as dual homogeneous coordinates. The motivation for why they are dual is presented in a later section.

The line at infinity

In the same way as there are points at infinity there is also a line at infinity, although only one line at infinity. The line at infinity is the result of considering the limit case of ${\sqrt {L_{1}^{2}+L_{2}^{2}}}\rightarrow 0$ in the transformation rule from $\mathbf {l}$ to the line parameters. The resulting line will have a distance to the origin which goes to infinity and have a homogeneous representation according to

$\mathbf {l} ={\begin{pmatrix}0\\0\\1\end{pmatrix}}$

Any homogeneous representation of a proper line has this vector as its limit value which means that there is only one line at infinity. It must also be the case that the line at infinity passes through all points at infinity and no other points.

The point at the intersection of two lines

Given the above homogeneous representation of points and lines we may ask the following question:

Let $\mathbf {l} _{1}$ and $\mathbf {l} _{1}$ be the dual homogeneous representations of two lines. What operation on $\mathbf {l} _{1}$ and $\mathbf {l} _{1}$ results in the homogeneous representation $\mathbf {x}$ of the intersection point of the two lines?

The answer is

$\mathbf {x} =\mathbf {l} _{1}\times \mathbf {l} _{2}$

To see that this is correct we can see that the above computation of $\mathbf {x}$ leads to

$\mathbf {x} \cdot \mathbf {l} _{1}=0\Rightarrow$ The point intersects the line represented by $\mathbf {l} _{1}$.

$\mathbf {x} \cdot \mathbf {l} _{2}=0\Rightarrow$ The point intersects the line represented by $\mathbf {l} _{2}$.

To summarize: the point intersects both lines. If the two lines are distinct, there can only be one point which intersects both lines and its homogeneous representation is then given by the cross product of the two lines' dual homogeneous representations.

From the outset, the practical implementation for finding the answer to the above question of intersection point needs to distinguish between three different cases:

1. The two lines are distinct and not parallel. The point of intersection is a proper point
2. The two lines are distinct and parallel. In standard geometry, no intersection point exists for this case. If, however, we extend the set of proper points with the points at infinity, two parallel line intersect in a point at infinity determined by the orientation of the lines. Intuitively, we can think of the points at infinity as a circle which is at infinite distance from the origin. Seen from this circle, the two parallel lines will appear as one even if they are distinct and moving along these two lines along either of the two direction all the way to infinity eventually makes them intersect with the circle at a point, a point at infinity. If we instead move along the lines in the other direction they will intersect the circle at a point on the opposite side. To avoid having two intersection points, we simple identify points which are on opposite sides of the circle. This makes is possible to define a unique point of intersection for the case of distinct and parallel lines.
3. The two lines are equal, there is one single line. In this case all points which lie on the line lie on both lines and are by definition intersection points, which means that the result is ambiguous. The best option in the context of a homogeneous representation is to produce the zero vector in this case, as a flag of ambiguous result.

A nice property of the homogeneous representations of points and lines is that the computation $\mathbf {l} _{1}\times \mathbf {l} _{2}$ encompasses all three cases, i.e., there is no need for if-clauses that performs different computations depending on which of the three cases we have. Assuming that we are dealing with two proper lines, if they are distinct and not parallel, the cross product will give the homogeneous representation of a proper point. If the lines are distinct and parallel, the cross product produces a point at infinity. If the lines are equal the cross product gives a zero vector. In fact, this computation work also if one or both lines are at infinity. If one is a proper line and the other the line at infinity, the result is a point at infinity. If both lines are at infinity, they must be equal, since there only is one such line, and the result is the zero vector.

The line which intersects two points

We may also ask the question:

Let $\mathbf {x} _{1}$ and $\mathbf {x} _{1}$ be the homogeneous representation of two points. What operation on $\mathbf {x} _{1}$ and $\mathbf {x} _{1}$ results in the dual homogeneous representation $\mathbf {l}$ of the line which intersects both points?

The answer is

$\mathbf {l} =\mathbf {x} _{1}\times \mathbf {x} _{2}$

To see that this is correct we can see that the above computation of $\mathbf {l}$ leads to

$\mathbf {l} \cdot \mathbf {x} _{1}=0\Rightarrow$ The line intersects the point represented by $\mathbf {x} _{1}$.

$\mathbf {l} \cdot \mathbf {x} _{2}=0\Rightarrow$ The line intersects the point represented by $\mathbf {x} _{2}$.

To summarize: the line intersects both points. If the two points are distinct, there can only be one line which intersects both points and the dual homogeneous representation is then given by the cross product of the two points' homogeneous representations.

In the case of determining the common line that intersects two points we only need to distinguish between two cases

1. The points are distinct. In this case there is always a unique line which intersects the points
2. The points are equal, there is one single point. In this case all lines passing through the point are intersecting both points, which means that the result is ambiguous. The result should be the zero vector.

The cross product $\mathbf {l} =\mathbf {x} _{1}\times \mathbf {x} _{2}$ includes both cases in the same computation. Assuming that both points are proper, the result is a proper line if they are distinct and the zero vector if they are equal. If one point is a proper point and the other a point at infinity, the cross product gives a proper line which always passes through the origin. If both points are at infinity, the result is the line at infinity.

Transformations of 2D points

Having defined homgeneous representations for points and lines in 2D, in terms of vectors in $\mathbb {R} ^{3}$, it is straight-forward to define homogeneous representation also for various types of coordinate transformations on these objects, in terms of linear transformations on these vectors, which conveniently are represented by $3\times 3$ matrices.

Translations

Let

$x={\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}$

be the coordinates of a point in 2D. This point may be translated or displaced by adding some quantities $(d_{1},d_{2})$ to the two coordinates, resulting in new coordinates

$x'={\begin{pmatrix}x'_{1}\\x'_{2}\end{pmatrix}}={\begin{pmatrix}x_{1}+d_{1}\\x_{2}+d_{2}\end{pmatrix}}$

The operation of translating coordinates is not a linear transformation; translating each of two points and then adding them is not the same as first adding the points and then translating the result. Consequently, we cannot represent the translation operation in terms of a linear transformation on the coordinate vector $x$.

In terms of the homogeneous representation of $x$ and $x'$ we seen that

$\mathbf {x} '={\begin{pmatrix}x'_{1}\\x'_{2}\\1\end{pmatrix}}={\begin{pmatrix}x_{1}+d_{1}\\x_{2}+d_{2}\\1\end{pmatrix}}={\begin{pmatrix}1&0&d_{1}\\0&1&d_{2}\\0&0&1\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\1\end{pmatrix}}$

This suggests that the translation operation can be represented as the matrix $\mathbf {T} (d_{1},d_{2})$ multiplied on $\mathbf {x}$, the homogeneous representation of $x$:

$\mathbf {x} '=\mathbf {T} (d_{1},d_{2})\,\mathbf {x}$

where

:$\mathbf {T} (d_{1},d_{2})={\begin{pmatrix}1&0&d_{1}\\0&1&d_{2}\\0&0&1\end{pmatrix}}$

This implies that the translation operation can be implemented as a linear transformation if it is applied to the homogeneous representation of points. This also implies that

$\mathbf {T} (d_{1},d_{2})\mathbf {T} (d_{1}',d'_{2})=\mathbf {T} (d_{1}+d'_{1},d_{2}+d'_{2})$

which can be verified by a simple matrix calculation

$\mathbf {T} (d_{1},d_{2})\mathbf {T} (d_{1}',d'_{2})={\begin{pmatrix}1&0&d_{1}\\0&1&d_{2}\\0&0&1\end{pmatrix}}\,{\begin{pmatrix}1&0&d'_{1}\\0&1&d'_{2}\\0&0&1\end{pmatrix}}={\begin{pmatrix}1&0&d_{1}+d'_{1}\\0&1&d_{2}+d'_{2}\\0&0&1\end{pmatrix}}=\mathbf {T} (d_{1}+d'_{1},d_{2}+d'_{2})$

Rotations

If $x'$ is obtained from $x$ and $x'$ as a rotation around the origin, their coordinates are related as

$x'={\begin{pmatrix}x'_{1}\\x'_{2}\end{pmatrix}}={\begin{pmatrix}\cos \alpha x_{1}-\sin \alpha x_{2}\\\sin \alpha x_{1}+\cos \alpha x_{2}\end{pmatrix}}={\begin{pmatrix}\cos \alpha &-\sin \alpha \\\sin \alpha &\cos \alpha \end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}$

This transformation rotates $x$ counter-clockwise to $x'$ with the angle $\alpha$ (means clockwise rotation if $\alpha <0$). The homogeneous representations are then related according to

$\mathbf {x} '={\begin{pmatrix}x'_{1}\\x'_{2}\\1\end{pmatrix}}={\begin{pmatrix}\cos \alpha &-\sin \alpha &0\\\sin \alpha &\cos \alpha &0\\0&0&1\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\1\end{pmatrix}}=\mathbf {R} (\alpha )\mathbf {x}$

where

:$\mathbf {R} (\alpha )={\begin{pmatrix}\cos \alpha &-\sin \alpha &0\\\sin \alpha &\cos \alpha &0\\0&0&1\end{pmatrix}}$

Rotation around an arbitrary point

A general rotation, around an arbitrary point $x_{0}$, can be seen as a combination of first translating the origin to $x_{0}$, then rotating followed by a translation back to the original coordinate system.