From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Q: general formula for area of polygon
Date: 24 Mar 1995 18:11:47 GMT

In article <3kuoje$spf@magellan.cloudnet.com>,
Jeff Hoffmann <hoffmann@cloudnet.com> wrote:
>i'm looking for an algorithm to find the area of a polygon formed by
>a series of connected points.  

This question has arisen before (and is likely to arise again). Here is
a lightly-edited version of a post I once made showing how to compute
not only the area but the center of mass. Of course, these can be computed
using surface integrals: one integrates  1, x, or  y over the region.
However, it is useful to use Green's theorem:
         _                   _
       _/  P dx + Q dy  =  _/   (dQ/dx - dP/dy) dxdy

so we can get the surface integrals of  1,  x,  and  y  respectively by
integrating  x,  x^2/2,  and  xy  w.r.t. y along the curve describing the
exterior of the polygon.

You'll need to know that the curve joining two points (x0 y0) and (x1, y1)
has a parameterization   (x,y) = ( (1-t) x0 + t x1,  (1-t) y0 + t y1 )
so that  dy = (y1 - y0) dt. Thus, the integral of   x dy along this
curve is  integral_[0,1]  ( (1-t) x0 + t x1 ) . (y1-y0) dt   which
comes out to  (x0+x1)/2 . (y1-y0). Compute this product over all consecutive
pairs of vertices (don't forget to rejoin the last to the first) and
you'll have the area of the polygon.

Likewise you can compute the integrals of  x^2/2  and  xy  on this curve;
if I haven't messed up, the first is  (x0^2 + x0 x1 + x1^2)/6 . (y1-y0)  
and the latter is  ( (y0 x1 + x0 y1) + 2(x1 y1 + x0 y0) )/6 . (y1 - y0).

So here's a procedure to find the enclosed area:

Clear counters  Area, Xcoord, Ycoord.
For each  i= index of the points x[i], y[i], do the following:
	Let  x0=x[i], y0=y[i]
	Let  x1=x[i+1], y1=y[i+1], where  i+1=first index if  i=last
	Compute factors  a1=(x0+x1)/2,
		a2=(x0^2+x0x1+x1^2)/6, and
		a3=(x0y1+y0x1+2(x1y1+x0y0))/6, as well as
		b=y1-y0
	Adjust counters Area=Area+a1. b,
		Xcoord=Xcoord+a2. b,  and
		Ycoord=Ycoord+a3. b.

At the end, the counter  Area  contains the area of the polygon;
the center of mass is at  (Xcoord/Area,  Ycoord/Area).

Of course if all you want is the area, you don't need to compute  a2  and  a3.
In this case you get some simplification: Area=(1/2)Sum y[i]*(x[i-1]*x[i+1]),
where the sum is taken cyclically around the polygon.

If you need to do this computation very often (i.e. you need it fast each
time) it makes sense to keep various partial products handy; I'll
leave this to professional programmers. 

dave

==============================================================================

From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Q: general formula for area of polygon
Date: 24 Mar 1995 20:20:02 GMT

In article <3kv213$8rk@watson.math.niu.edu>, I wrote:
>>i'm looking for an algorithm to find the area of a polygon formed by
>>a series of connected points.  
...
>So here's a procedure to find the enclosed area:

Of course I should point out that there is some cancellation in the area
computation, so if that's all you want, you can do it a bit more
cleanly as  Area = (1/2) Sum( y[i]*(x[i-1]-x[i+1]) ), the sum taken cyclically
around the polygon. Moreover, I should be careful to state that this gives
the _signed_ area: in Green's theorem it is assumed that you walk around
the curve with the interior on your left. (Thus you will need to know that
the curve does not self-intersect, unless you don't mind getting an answer
which represents a signed area).

(When computing the center of mass, we are taking the quotient of two
such line integrals, and so assuming the curve does not self-intersect, a 
sign error in the two will cancel each other out.)

dave