Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!ginosko!uunet!zephyr.ens.tek.com!tekcrl!tekgvs!tekirl!jackg
From: jackg@tekirl.LABS.TEK.COM (Jack Gjovaag)
Newsgroups: comp.graphics
Subject: Re: Need an algorithm to calculate area of polygons
Keywords: Polygon, algorithm
Message-ID: <6059@tekgvs.LABS.TEK.COM>
Date: 4 Oct 89 21:14:47 GMT
References: <484@ctycal.UUCP> <619@cditi.UUCP>
Sender: nobody@tekgvs.LABS.TEK.COM
Reply-To: jackg@tekirl.LABS.TEK.COM (Jack Gjovaag)
Organization: Tektronix, Inc., Beaverton,  OR.
Lines: 39

In article <484@ctycal.UUCP>, ingoldsb@ctycal.COM (Terry Ingoldsby) writes:
> I need an algorithm that will calculate (quickly)
> the area of an arbitrary polygon.  It would be *nice* if it could
> handle objects that include arcs, instead of lines for the edges of
> the `polygon'.  I have to be able to handle complicated cases like
> 
>          *--------------------------*
>          |         *________________|
>          |         |
>          |         *_______*
>          |                / 
>          *_____*        /
>               /       /      It's hard to draw diagonal lines!
>             */------*
> 
> -- 
>   Terry Ingoldsby                       ctycal!ingoldsb@calgary.UUCP
>
If you have the polygon described in terms of an ordered
list of n vertices (x(i), y(i)), where i=1 to n, and where
(x(n), y(n)) = (x(1), y(1)), i.e., the first point of the
list is duplicated at the end of the list, then the area
can be found by the following formula:

A = abs(sum (i=1 to n) (x(i+1)-x(i))*(y(i+1)+y(i))/2)

If the edges of the polygon cross, then the value of A won't mean
much. Removing the absolute value function and looking at
the sign of the sum will tell you if the polygon was
described in a clockwise (>0) or counterclockwise (<0)
direction.  Since each term of the sum is the 
signed area under the segment describing an edge, the
formula can be generalized to edges other than straight
line segments by replacing the appropriate terms with
the definite integral representing the signed area
under the curve segment.

  Jack Gjovaag
  Tek Labs