[comp.graphics] Need to find polygon direction

jtevik@gisplot1.nrri.umn.edu (John Tevik) (12/10/90)

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).

Thanks in advance.

John Tevik                        jtevik@gisplot1.nrri.umn.edu (128.101.45.101)
Programmer                        jtevik@madonna.d.umn.edu (131.212.32.9)
University of Minnesota           (218)720-4247 (voice)
Natural Resources Research Institute

gordon@cs.tamu.edu (Dan Gordon) (12/10/90)

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.

lambert@spectrum.cs.unsw.oz.au (Tim Lambert) (12/10/90)

>>>>> On 9 Dec 90 19:40:14 GMT, jtevik@gisplot1.nrri.umn.edu (John Tevik) said:

> Here's one for the FAQ.  I need to find the direction (whether clockwise or
> counter-clockwise) of a 2D polygon.

Calculate the *signed* area:

  A = 0.5*\sum_{i=1,2..n} x_i * (y_{i+1} - y_{i-1})

This is positive if and only if the polygon is anti-clockwise.
(This is faster than calculations involving angles.)

Tim

jack@shograf.UUCP (Jack Ritter) (12/14/90)

In article <LAMBERT.90Dec11000343@nankeen.spectrum.cs.unsw.oz.au>, lambert@spectrum.cs.unsw.oz.au (Tim Lambert) writes:
> >>>>> On 9 Dec 90 19:40:14 GMT, jtevik@gisplot1.nrri.umn.edu (John Tevik) said:
> Calculate the *signed* area:
>   A = 0.5*\sum_{i=1,2..n} x_i * (y_{i+1} - y_{i-1})

The question of polygon handedness seems to come
up frequently. Look in the upcomming "More Graphics Gems"
for what I feel is the fastest method for (convex) polys:
  "Fast Sign of Cross Product Calculation".

p_davis@epik.enet.dec.com (Peter Davis) (12/14/90)

In article <295@shograf.UUCP>, jack@shograf.UUCP (Jack Ritter) writes...
>Look in the upcomming "More Graphics Gems"
>for what I feel is the fastest method for (convex) polys:
>  "Fast Sign of Cross Product Calculation".

Any news about this book?  When's it scheduled to be published?  When can I get
a copy?  If it's as good as the first one, I want it now.  Also, will the
sources be put on the net, as the first set was?

Thanks.
-pd