Algorithm for Area of a closed polygon.

[Jeffrey_Danowitz at amat.com]

Hi!
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.

Yours,
Jeff






Gill Barequet <barequet at cs.technion.ac.il>
11/13/2003 12:07 AM

 
        To:     compgeom-discuss at research.bell-labs.com, thill at tomotherapy.com
        cc: 
        Subject:        Re: Algorithm for Area of a closed polygon.
 


On Wed, 12 Nov 2003 08:59:37 "Ted Hill" <thill at 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 at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://compgeom.poly.edu/pipermail/compgeom-announce/attachments/20031113/68b4cef9/attachment.htm