Re: Algorithm for Area of a closed polygon.

[Gill Barequet <barequet@cs.technion.ac.il>]

On Wed, 12 Nov 2003 08:59:37 "Ted Hill" <thill@tomotherapy.com> wrote:

> I want to be able to calculate the area inside a closed many-sided polygon.
> Given an array of the (x,y) vertices that define the polygon, is there a
> well-known algorithm that can calculate the enclosed area quickly?

Use the well-known sailor's algorithm: Assume wlog that the polygon is above
the X axis. Project all the polygon's edges to the X axis, and sum up the
signed areas of all the induced trapezoids. (Set the sign of a trapezoid
acoording to whether or not the inducing oriented edge goes from left to right.)

(Theoretically you can compute the area in linear time also by triangulating
the polygon and summing up the areas of the triangles... 8-)

Gill

-------------
The compgeom mailing lists: 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.