Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!helios!gordon
From: gordon@cs.tamu.edu (Dan Gordon)
Newsgroups: comp.graphics
Subject: Re: Need to find polygon direction (cw/ccw)
Keywords: polygon direction
Message-ID: <10749@helios.TAMU.EDU>
Date: 9 Dec 90 21:15:45 GMT
References: <548@ub.d.umn.edu>
Sender: news@helios.TAMU.EDU
Organization: Computer Science Department, Texas A&M University
Lines: 31

In article <548@ub.d.umn.edu> jtevik@gisplot1.nrri.umn.edu (John Tevik) writes:
>Here's one for the FAQ.  I need to find the direction (whether clockwise or
>counter-clockwise) of a 2D polygon.  I'm writing a program to translate
>census tract data into SPSS Graphics and need to find the direction of
>each polygon to properly assign left and right area ID's.  Polygons are
>normally closed and are represented as a linked list of coordinate pairs
>This exact problem is left as an exercise in Foley & van Dam (problem 
>A.3.a pg. 1112).

Hint: imagine that you are walking along the perimeter. At every vertex,
you have to turn in order to walk along the next edge. Sum up all the 
angles of rotation so that at the end of the walk you are in your
initial position and facing the exact same direction that you started.
A left turn is considered positive (counter clockwise), a right turn
is considered negative. Assuming that the edges do not intersect, if
the sum is 360 degrees, the polygon is CCW; if the sum is -360, the
polygon is CW. Example:
		|
		|
		|-90
		--------->-----------
		|		|-90
		|		|
		^		v	Sum of angles = -360
		|		|	Direction: clockwise.
	     -90|		|
	    -------------<------|
			     -90|
				|

BTW, if the sum is zero, then the edges intersect an odd number of times.