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 xt and yt are the coordinates of the tail point and xh and yh are those of the head point. The determinant evaluates to xtyh – xhyt. 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.
It’s a version of Green’s theorem (turning the integral of the constant function 1 over the area of the polygon into something over the perimeter). It can be interpreted as summing the areas of triangles determined by the origin and the two endpoints of each edge.
I usually teach something like this in my algorithms and computational geometry classes, but I use the similar formula 1/2 sum((x_{i+1}-x_i)(y_i+y_{i+1})) which uses half as many multiplication operations. It can be interpreted as summing the areas of with vertical sides between each edge and the x axis.
See also the comp.graphics.algorithms faq, question 2: http://www.faqs.org/faqs/graphics/algorithms-faq/
Thanks for both the illumination and the pointers.
“A version of Green’s theorem” — Conceptually, sure, but I trust you don’t mean to suggest that the line-integral formulation came first historically, and the discrete algorithm was derived from it? For one thing, that would put the origin sometime after 1828.
The simplest version of this is to consider a parallelogram and notice that if one corner is the origin then only two other points are needed to define the parallelogram. Furthermore, these points can be regarded as vectors and be entered as rows or columns in a matrix whose determinant is then the area of the parallelogram.
The area of a convex polygon can then be found by placing the origin in the center, chopping the polygon into triangles (which are halves of parallelograms), and then doing the above parallelogram trick over and over. I wonder if the same thing can be done with three dimensional polytopes using three by three matricies.
this was so awesome. i deff. used it to do a project. wicked cool. thanx