5
$\begingroup$

I was looking for a solution for finding two intersecting lines. I am aware that this can be done by finding a vector product of two lines.

I have stumbled upon this example here: https://stackoverflow.com/a/42727584

I have gone through the example and used it in a few scenarios and it seems to work pretty well. However, there are three things I don't quite get:

  1. Why does the vector need to be homogeneous (the part where we fill a column with ones)?
  2. How does the homogeneous solution differ compared to a non-homogeneous solution (if at all)?
  3. How come we only check the result for parallelism along the Z-axis and not X and Y as well?

I feel like I am missing something very obvious but I can't wrap my head around on what it is.

$\endgroup$

2 Answers 2

4
$\begingroup$

Homogeneous coordinates for points and lines in the Euclidean plane are convenient because

  • the line $l$ through two points $p_1$ and $p_2$ is easy to compute: $l = p_1 \times p_2$
  • the intersection point $p$ of two lines $l_1$ and $l_2$ is easy to compute: $p = l_1 \times l_2$
  • you get an intersection point for any pair of distinct lines, even parallel ones. For them the $z$ coordinate of the intersection point will be $0$ so you cannot dehomogenize them (which is reasonable because parallel lines have no intersection point in Euclidean geometry). These points are called “points at infinity” or “ideal points”.

So to answer your questions:

  1. Its convenience for an easy implementation without any conditions until the very end.
  2. When a non-homogeneous solution $(x,y)$ exists the homogeneous one will be $\lambda \cdot (x,y,1)$ for a $\lambda \in \mathbb R \backslash \{0\}$. And for a homogeneous solution $(x,y,0)$ there exists no non-homogeneous one.
  3. You only have to check the homogeneous coordinate (the one you want to divide through) for zero.
$\endgroup$
1
  • $\begingroup$ A short yet perfect answer for my question, thank you very much! $\endgroup$ Commented May 9, 2019 at 9:14
3
$\begingroup$

A convenient way to visualize what’s going in is one of the standard models of the projective plane.

By adding a third coordinate of $1$, you’re identifying the Euclidean plane $\mathbb R^2$ with the plane $z=1$ in $\mathbb R^3$. Nothing special there yet. However, these coordinates are homogeneous: for any $k\ne0$, $(x,y,1)$ and $(kx,ky,k)$ represent the same point.† In terms of this $z=1$ plane model, what we’ve done is identify a point in $\mathbb R^2$ with the line through the origin and corresponding point in the $z=1$ plane in $\mathbb R^3$. (Actually, we omit the origin and work in $\mathbb R^3\setminus\{0\}$, but that’s not critical to the concepts here.) Homogeneous coordinates of a point are therefore direction vectors of the corresponding line.

Now consider a line in $\mathbb R^2$. This maps to a line on our $z=1$ reference plane, and the union of all of the lines through the origin and points on this line form a plane $\mathbf\pi$ through the origin. There is a unique line through the origin that is perpendicular to $\mathbf\pi$, so we can identify the plane with the set of direction vectors of this unique perpendicular, i.e., with the normal vectors to $\mathbf\pi$. The upshot of this is that we can assign a unique set of homogeneous coordinates to each line in $\mathbb R^2$. Moreover, if we have any two linearly-independent vectors $\mathbf p$ and $\mathbf q$ on $\mathbf\pi$, $\mathbf p\times\mathbf q$ is normal to $\mathbf\pi$, that is, we can obtain homogeneous coordinates of a line by computing the cross product of any homogeneous coordinates of a pair of distinct points on the line.

Similarly, homogeneous coordinates of intersection of two lines in $\mathbb R^2$ can be found by computing the cross product of the two lines’ homogeneous coordinates: Two distinct planes through the origin in $\mathbb R^3$ intersect in a line through the origin that’s perpendicular to the normals of both planes. (This is one example of point-line duality on the projective plane.)

What happens if the lines in $\mathbb R^2$ that these planes represent are parallel? It should be easy to see that their intersection lies on the $x$-$y$ plane—the direction vectors of this intersection line all have a $0$ $z$-coordinate. These lines are perfectly sensible objects in our model, though. They only seem special because they’re parallel to our embedded plane. Similarly to the way complex numbers were useful as intermediate results when finding real roots of cubics, these “extra” lines are useful intermediate results in geometrical computations. For example, to find the line through a point $\mathbf p$ that is parallel to our two parallel lines $\mathbf l_1$ and $\mathbf l_2$, we need only compute $\mathbf p\times(\mathbf l_1\times\mathbf l_2)$. There’s no particular reason to treat these lines any differently from lines that go through the $z=1$ plane, so we make them first-class citizens by adding a “point at infinity” to $\mathbb R^2$ for each of them. For completeness, we also add a “line at infinity,” represented in $\mathbb R^3$ by the plane $z=0$ (i.e., with homogeneous coordinates $(0,0,1)$), that contains all of these new points. Each of these points is the common intersection of a family of parallel lines in $\mathbb R^2$. In a sense, then, points at infinity represent directions in $\mathbb R^2$.

The upshot of all this is that when you compute the intersection of two lines in $\mathbb R^2$ by taking the cross product of their homogeneous coordinates, if the third coordinate of the result is $0$, then the lines are parallel. This also makes sense from a purely mechanical point of view: to “dehomogenize” the result, you have to divide through by the third coordinate, but it it’s zero the result is undefined—there’s no finite point that is the intersection of the two lines.

What makes the $z$-coordinate special here is the choice that we made when we embedded $\mathbb R^2$ into $\mathbb R^3$ as the $z=1$ plane. This made the $z$-coordinate the “extra” one in the homogeneous coordinates of a point. We could just as well have used the $x=1$ plane instead, which would’ve made the $x$-coordinate the “extra” one (in fact, you’ll see this in some sources). For that matter, we could’ve chosen any plane not through the origin for the embedding. The points at infinity would still be lines that parallel the plane, but identifying them from their direction vectors is less convenient that checking a single value for zero.


† In effect, we really care about the ratios among the coordinates, which is why you’ll sometimes see homogeneous coordinates written as $x:y:z$.

$\endgroup$
4
  • $\begingroup$ Thank you for your detailed answer, it's superb for understanding the background behind the concept. I wish I could choose two best answers, the only reason I chose the other one was due to its simplicity. $\endgroup$ Commented May 9, 2019 at 9:16
  • 1
    $\begingroup$ I’ll also note that this is what I would call a “bottom up” construction. One can also start with the projective plane, in which all lines intersect in a unique point, and then impose an affine geometry by singling out one of the lines as the line at infinity. $\endgroup$
    – amd
    Commented May 9, 2019 at 19:27
  • $\begingroup$ Thank you for noting that! $\endgroup$ Commented May 10, 2019 at 7:37
  • 1
    $\begingroup$ In that comment, I should’ve written that every pair of lines intersects in a unique point—I didn’t mean that all lines are incident. $\endgroup$
    – amd
    Commented May 10, 2019 at 7:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .