Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cwjcc!delta!bond
From: bond@delta.CES.CWRU.Edu (angus bond)
Newsgroups: comp.graphics
Subject: Re: Need an algorithm to calculate area of polygons
Keywords: Polygon, algorithm
Message-ID: <761@cwjcc.CWRU.Edu>
Date: 5 Oct 89 19:03:35 GMT
References: <484@ctycal.UUCP>
Sender: news@cwjcc.CWRU.Edu
Reply-To: bond@delta.UUCP (angus bond)
Organization: CWRU Dept of Computer Engineering and Science, Cleveland, OH
Lines: 38

I see that a lot of replys to this question suggest breaking the polygon
down into triangular pieces.  This is not necessary.  I also wish I had
a copy of Newmann and Sproul handy to see if the solution I am proposing
matches theirs.  But here goes...

I found this algorithm in the _Handbook_of_Mathematical_Tables_ published
by the Chemical Rubber Company, affectionately referred to as the CRC
Math Tables book.  Every edition has this algorithm in it.  I don't have
it handy so you will have to go get the book or a similar one to get the
precise scoop.  The formula is sort of like a laterally extended 2x2
determinant:
	     -  -  -       -   -
	    /  /  /       /   /
	xn x1 x2 x3 ... xn-1 xn
	yn y1 y2 y3 ... yn-1 yn
	    \  \  \       \   \
	     +  +  +       +   +

That is, 

	(xn * y1) + (x1 * y2) + (x2 * y3) + ... + (xn-1 * yn) 
	- (yn * x1) - (y1 * x2) - (y2 * x3) - ... - (yn-1 * xn)

This formula (provided I remembered it correctly), gives the area of the
polygon formed by the points (x1,y1), (x2,y2), ... (xn, yn).  If the curve
crosses itself, it subtracts the area of the reversed section.  Order the
points one way and you get a positive area; order them the other way and
you get a negative area.  This equation works for any number of points.

One thing I don't know is how well this formula handles round-off errors
for large n.  It does work well for reasonable values of n.

I hope this helped.

Angus Bond
bond@alpha.cwru.edu (did I get my address right?)
school: (216) 368-5506
work:   (216) 349-2548