Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!uw-entropy!stuart!bill
From: bill@stuart.stat.washington.edu (Bill Dunlap)
Newsgroups: comp.graphics
Subject: Re: Need an algorithm to calculate area of polygons
Keywords: Polygon, algorithm
Message-ID: <2273@uw-entropy.ms.washington.edu>
Date: 4 Oct 89 18:52:01 GMT
References: <484@ctycal.UUCP> <619@cditi.UUCP>
Sender: news@uw-entropy.ms.washington.edu
Reply-To: bill@stuart.UUCP ()
Organization: UW Statistics, Seattle
Lines: 22

In article <619@cditi.UUCP> josh@cditi.UUCP (Josh Muskovitz) writes:
>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.
>
>You should be able to pick an arbitrary point in the plane, and build a list
>of triangles from every pair of adjacent endpoints.  The trick is determining
>whether to add or subtract the area of the tirangle from the ongoing subtotal.

1/2 * sum( x(i)*y(i-1) - y(i)*x(i-1) ), wrapping the indexes around the ends
will give the (signed) area of a polygon.  The sign is positive if the
vertices are given clockwise.  Each summand is the signed area of a triangle
with one edge an edge of the polygon and the remaining vertex (0,0).

Note the similarity to Green's (or is it Stoke's?) theorem in calculus
which relates an integral over a boundary to an integral over the area
within that boundary.




	Bill Dunlap