Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!watmath!watcgl!ksbooth
From: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Newsgroups: comp.graphics
Subject: Re: Need an algorithm to calculate area of polygons
Keywords: Polygon, algorithm
Message-ID: <11848@watcgl.waterloo.edu>
Date: 10 Oct 89 17:41:11 GMT
References: <484@ctycal.UUCP> <619@cditi.UUCP> <2273@uw-entropy.ms.washington.edu> <9885@thorin.cs.unc.edu>
Reply-To: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Organization: U. of Waterloo, Ontario
Lines: 22

In article <9885@thorin.cs.unc.edu> airey@matisse.cs.unc.edu (John Airey) writes:
>In article <2273@uw-entropy.ms.washington.edu> bill@stuart.UUCP () 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.
>                   ^^^^^^^^^
>
>If arbitrary means possibly concave, the following suggestion is inadequate.
>
>>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).
>>	Bill Dunlap

The formula works.  It is Newell's formula.  It handles concave polygons
quite well.  It can be derived by an easy induction starting with the formula
for the cross product of two vectors and the fact that this gives the area
of the parall..gram (I never could spell this!) defined by the two vectors.

The algorithm is "optimal" in the sense that it looks at each vertex only
once and does a relatively small amount of work for each.