Algorithm for Area of a closed polygon.

Jeffrey_Danowitz at Jeffrey_Danowitz at
Thu Nov 13 11:44:36 PST 2003

Perhaps this is equivalent to Gill's idea. Pick any vertex on the polygon. 
No need to assume anything except that the array, p, of vertices is in 
polygonal order, which it usually the case. From that point, build 2 
vectors (p(b),p(b+1)), (p(b),p(b+2)) and take half the cross product 
(signed area). Continue around taking vectors (p(b),p(b+i)) and 
(p(b),p(b+i+1)) i=2,...n-1, summing the signed areas as you go along. 
In the end take the absolute value -- and this is the area. 
If you think about it, this is just Green's theorem in action.  Clearly 
this is a linear algorithm.

I hope my description is clear.


Gill Barequet <barequet at>
11/13/2003 12:07 AM

        To:     compgeom-discuss at, thill at
        Subject:        Re: Algorithm for Area of a closed polygon.

On Wed, 12 Nov 2003 08:59:37 "Ted Hill" <thill at> wrote:

> I want to be able to calculate the area inside a closed many-sided 
> 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 
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 

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


The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Compgeom-announce mailing list