Path: utzoo!utgpu!watmath!watcgl!ksbooth
From: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Newsgroups: comp.graphics
Subject: Re: Computational geometry II
Message-ID: <9458@watcgl.waterloo.edu>
Date: 30 Apr 89 02:40:57 GMT
References: <2053@incas.UUCP> <5397@cs.utexas.edu> <9455@watcgl.waterloo.edu>
Reply-To: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Organization: U. of Waterloo, Ontario
Lines: 15

P.S.  The algorithm presented in

article <5397@cs.utexas.edu> by atc@cs.utexas.edu (Alvin T. Campbell III)

is typical of most of these "solutions".  It walks the entire polygon looking
for the "top" vertex (incorrectly, as it turns out, but making it right takes
even more code), when Newell's formula would perform a fairly simple (but
floating-point, to be sure) calculation at each vertex and be done with it.

For quadrilaterals and triangles (by far the most common cases), I believe
the total computation is less for the Newell's formula.  As the number of
vertices gets large, Newell's formula may lose, but in these cases the
chance of "bad" data increases, so Newell's formula is even more appropriate.
(And if you only want the orientation, you don't have to compute all three
coefficients, just c).