Algorithm for Area of a closed polygon.
Jeffrey_Danowitz at amat.com
Jeffrey_Danowitz at amat.com
Thu Nov 13 11:44:36 PST 2003
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
More information about the Compgeom-announce
mailing list