Thursday, April 02, 2009

Homogeneous Coordinates in the Extended Euclidean Plane

I've discussed the Extended Euclidean Plane ("EEP") before. Now I want to talk about homogeneous coordinates, because they are just very cool and convenient. They are used in all field planes, but the EEP works well as something to blog about without having to go into a whole bunch of other "stuff." (But in particular, we use them in a lot of finite field planes - that is, planes defined over a field that has a finite number of members rather than a field like the real numbers.)

So, the main distinguishing feature of the EEP is that there are no parallel lines. Lines that are parallel in the Euclidean plane meet at a "point at infinity" associated with their slope. These different points at infinity (one for each possible slope of line) make up the "line at infinity."

Normally, when we talk about coordinates in the Euclidean Plane, we use two numbers, so for instance, (2,3) might be the coordinates of a point. But for homogeneous coordinates, we are going to use three numbers - a 3-dimensional vector. What makes them "homogeneous" is that every scalar multiple of this vector refers to the same point, so that, for instance,

(1, 1, 1)

and

(2, 2, 2)

refer to the same point.

As a convention, we will make these coordinates from the usual Euclidean coordinates by making using the x and y values unchanged, and using 1 as the third coordinate. So the point formerly referred to as (2, 3) is now (2, 3, 1). It can also be called any scalar multiple of that, like (4, 6, 2) or (2/3, 1, 1/3), but there is no reason not to reduce any of those to (2, 3, 1).

Lines will also have three coordinates, which will come from the usual definition of a line:

y = 2x + 4

is the same as

2x - y + 4 = 0

and gives rise to homogeneous coordinates: [2, -1, 4]

A point is on a line iff the dot product of the vectors of the point and line is 0. So let's say we have the line y = 2x + 4, and the point (1, 6). The homogeneous coordinates for the line are [2, -1, 4] and for the point we have (1, 6, 1).

(1, 6, 1) (dot) [2, -1, 4] = 1 * 2 + 6 * -1 + 1 * 4 = 0

so the point is on the line as we expect. Note that this is the same thing as saying that a line with coordinates [a, b, c] has the equation

ax + by + cz = 0

and a point with coordinates (x, y, z) is on the line iff it satisfies that equation.

But what's with the three dimensions, yo? That doesn't make any sense.

The deal here is that we're kind of analogizing points (which usually have two coordinates) to lines (which usually have three), and lines to planes. Specifically, points become lines through the origin, and lines become planes through the origin. A point is on a line if the corresponding line is in the corresponding plane. Since two distinct lines through the origin determine a unique plane through the origin, and two distinct planes through the origin intersect in a unique line through the origin, this corresponds to our desired relationship between points and lines.

Now then. I've said that two parallel lines intersect at a point at infinity. How does that work? Well, let's look at these two parallel lines:

y = 2x + 1
y = 2x + 3

and, using the homogeneous coordinates, see them as a system of equations:

2x - y + z = 0
2x - y + 3z = 0

Using a bit of linear algebra (or regular algebra, if you prefer), we find that in order to solve these equations, a point (x, y, z) has to have the form (t, 2t, 0) for some t. So we can say that the homogeneous coordinates for this point are (1, 2, 0).

Using coordinates this way, in the EEP we will always get 0 as the final coordinate of a point on the line at infinity. The line at infinity, meanwhile, has homogeneous coordinates [0, 0, 1], as you can confirm if you like.

The linear algebraic qualities of this sytem mean that solving for the point of intersection of two lines, and for the line determined by two points, are exactly the same operation. In fact, given two line or point coordinates (a, b, c) and (d, e, f) we can solve for the point of intersection or the common line, respectively, by solving this determinant:

| x y z |
| a b c | = 0
| d e f |

i.e.,

(bf - ce)x - (af - cd)y + (ae -bd)z = 0

so the coordinates of the desired point or line are (bf - ce, cd - af, ae - bd).

So that's what I've been up to lately...