Path: utzoo!attcan!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: <11766@watcgl.waterloo.edu>
Date: 4 Oct 89 21:04:47 GMT
References: <484@ctycal.UUCP> <11765@watcgl.waterloo.edu>
Reply-To: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Organization: U. of Waterloo, Ontario
Lines: 17

In article <484@ctycal.UUCP> ingoldsb@ctycal.COM (Terry Ingoldsby) writes:
>This is probably a trivial problem, and one that has been much
>discussed, but I need an algorithm that will calculate (quickly)
>the area of an arbitrary polygon.

Use Newell's formula, which is in the appendix of the second edition of
Neuman and Sproull.  It works for any planar polygon (convex/concave,
simple/non-simple) and has the nice property that it gracefully
degrades when the polygon is not planar (due to roundoff errors in the
vertex coordinates or simply bad data to begin with).

For the special case n=3, this is just the cross product formula for
the area of a triangle (actually twice the area, you need to divide the
answer by two in all cases), given two vectors which form the base and
side of the parallelogram.  What you get is a vector whose magnitude is
the area of the polygon and whose direction is normal to the plane of
the polygon.