bit-player

Here’s an algorithm for finding the area of any simple polygon. First, assign an orientation to every edge by drawing an arrowhead pointing in the counterclockwise direction around the cycle of edges. After this labeling, each vertex of the polygon becomes the “tail” endpoint of one edge and the “head” endpoint of another. Now, for each edge, evaluate the following 2 × 2 determinant:

where x_t and y_t are the coordinates of the tail point and x_h and y_h are those of the head point. The determinant evaluates to x_ty_h – x_hy_t. The sum of all the determinants is twice the area of the polygon.

Question: Am I the only one who hasn’t always known about this algorithm? Did I pick the wrong day to skip school? I remember “one-half the base times the height” and various other fussy formulas for specific polygons, but I don’t believe I ever learned this method.

I belatedly got a clue from some excellent lecture notes (.ps.gz) by Jonathan Richard Shewchuk of the University of California at Berkeley. I gather that the algorithm is widely used in the computational-geometry community. Land surveyors also know it: I’ve found descriptions of what I think is essentially the same procedure in surveying manuals going back at least as far as 1808 (though without explicit mention of determinants). In 1986 Bart Braden of Northern Kentucky University wrote about the algorithm (and its extension to figures enclosed by continuous curves) for The College Mathematics Journal. So this isn’t really a new trick, and yet I have a sense it is not widely taught or employed. Or, again, maybe it’s just one of my personal blind spots.

In any case, I am grateful to know it now. It has a lot going for it:

• Generality. It offers one formula for any simple polygon (where “simple” means no self-intersections). The procedure is the same no matter what the number of edges, whether the polygon is regular or not, and whether it is convex or not.
• Robustness. The algorithm seems to be indifferent to many of the anomalies and degeneracies that plague lots of geometric methods. The position and orientation of the polygon on the plane are of no consequence mathematically (though they might affect numerical accuracy). Oddities such as zero-length edges cause no trouble. If you ask for the area of a polygon that’s been squashed flat, the procedure returns the sensible and correct answer of zero.
• Numerical niceness. The only arithmetical operations needed are multiplication, addition and subtraction, with just a single division by 2 at the end. There are no square roots, trig functions, or other sources of irrationality. Do the arithmetic exactly and you’ll get exact results.

What is the history of this method? Who discovered it? Does it have a name? Because it draws on concepts from coordinate geometry, I can’t see how the Greeks could have found it. What about Descartes and Fermat? Or did it have to wait for the full development of ideas about vectors, matrices and determinants?

Among the surveying manuals that mention the technique, this is the earliest I’ve found:

Flint, Abel. 1808. A System of Geometry and Trigonometry: together with a treatise on surveying: teaching various ways of taking the survey of a field; also to protract the same and find the area. Likewise, Rectangular Surveying; Or, an accurate method of calculating the area of any field arithmetically, without the necessity of plotting it. Second edition. Hartford: Oliver D. Cooke. (See pp. 59–94 on “rectangular surveying.”) [Google Books link.]

And this is the reference for Braden’s article, which among other things gives a proof of the algorithm’s correctness.

Braden, Bart. 1986. The surveyor’s area formula. The College Mathematics Journal 17(4):326–337.

Update: As soon as I posted the above, it occurred to me that the algorithm leads to an immediate proof that any polygon whose vertices lie on the lattice of integers must have for its area either an integer or a half-integer. This also follows from Pick’s Theorem (the point-counting method for finding the area of a lattice polygon). There’s a vast literature on Pick’s Theorem and lattice polygons, so maybe that’s a place to look for other discussions of this method.

Update 2007-02-04: A tipster has alerted me to another important reference: Gilbert Strang, “Polar Area is the Average of Strip Areas,” The American Mathematical Monthly, Vol. 100, No. 3. (Mar., 1993), pp. 250-254. There I find the following passage:

“Known but not well known,” says Strang. But evidently becoming better known, at least among Minnesota carpet layers.