Path: utzoo!attcan!uunet!know!cs.utexas.edu!sun-barr!newstop!exodus!peregrine!falk
From: falk@peregrine.Sun.COM (fred)
Newsgroups: comp.graphics
Subject: Re: Polygon orientation test ?
Message-ID: <1630@exodus.Eng.Sun.COM>
Date: 23 Oct 90 04:22:29 GMT
References: <4158.272311a1@cc.curtin.edu.au> <5201@crash.cts.com>
Sender: news@exodus.Eng.Sun.COM
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 22

In article <5201@crash.cts.com> jcs@crash.cts.com (John Schultz) writes:
>  Yes, there are at least two easy ways:
>
>    1. Use the cross product of two of the points, the sign determines
>       the orientation (Subtract point 0 from points 1 and 2, compute
>       the cross product between the new points 1 and 2).

Careful!  If the polygon isn't convex, you can easily get the wrong answer.

>    2. Use the Newell method (in many graphics texts).

This works.  Essentially, you use the standard algorithm for finding
the area of a polygon:

    A = .5 * ( (y1+y0)(x1-x0) + (y2+y1)(x2-x1) + ... + (y0+yn)(x0-xn) )

and look at the sign of the result.  That's all.


		-ed falk, sun microsystems
		 sun!falk, falk@sun.com
		 card-carrying ACLU member.