To: Ted Hill <thill@tomotherapy.com>
Subject: Re: Algorithm for Area of a closed polygon.
From: "Demian M. Nave" <dnave@psc.edu>
Date: Wed, 12 Nov 2003 21:23:16 -0500 (EST)
Cc: <compgeom-discuss@research.bell-labs.com>
In-reply-to: <1E2E66102E75104D8C740340EBCD98671BC279@tomoex.tomotherapy.com>
References: <1E2E66102E75104D8C740340EBCD98671BC279@tomoex.tomotherapy.com>
Reply-to: Demian Nave <dnave@psc.edu>
Hi Ted,
I want to be able to calculate the area inside a closed many-sided polygon.
As long as your polygon has no self-crossings or internal holes, this algorithm is probably the simplest. It will return twice the signed area of your polygon:
Let 'vertices' be an array of N pairs (x,y), indexed from 0
Let 'area' = 0.0
for i = 0 to N-1, do
Let j = (i+1) mod N
Let area = area + vertices[i].x * vertices[j].y
Let area = area - vertices[i].y * vertices[j].x
end for
Return 'area'
If the vertices of your polygon are specified in counter-clockwise order (i.e. by the right-hand rule), then the area will be positive. Otherwise, the area will be negative, assuming the polygon has non-zero area to begin with.
Hope this helps. Send another note to the mailing list if not. :-)
Cheers, Demian
Demian M. Nave | dnave@psc.edu | Ph 412 268-4574
Pgh. Supercomputing Center | www.psc.edu/~dnave | Fx 412 268-8200-
4400 Fifth Avenue | "When your work speaks for itself, don't
Pittsburgh, PA 15213 | interrupt." - Kanin
see http://netlib.bell-labs.com/netlib/compgeom/readme.html or send mail to compgeom-request@research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.