Path: utzoo!utgpu!watserv1!watmath!att!att!dptg!ulysses!andante!alice!td
From: td@alice.att.com (Tom Duff)
Newsgroups: comp.graphics
Subject: Re: clockwise or counter-clockwise 2d polygons
Summary: shorter solution.
Message-ID: <11524@alice.att.com>
Date: 23 Oct 90 13:42:44 GMT
References: <1990Oct22.114039.8799@jarvis.csri.toronto.edu>
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 34



Brent Corkum of Toronto posted a 165 line solution to somebody's
request for a polygon orientation (cw/ccw) test.  A much simpler
method is to compute the polygon's area by
summing trapezoid areas.  If the sum is positive, the vertices
are passed clockwise, otherwise they're passed counter-clockwise.

If a polygon is not simple (i.e. if its boundary intersects
itself) it may be impossible to assign a meaningful orientation.
In that case this method fails, as it ought to.  It does not deliver
a diagnostic in that case, as simplicity testing is a rather more
complicated problem than computing area -- increasing the size
of the code by a factor of 20 (just a guess, 50 may be more realistic)
for the sake of an error check would be silly.

Also, another poster (who will remain nameless) submitted a hilarious
proposal for finding the orientation of a polygon in 3-space.  In
3 dimensions, a polygon has no orientation:  if it appears clockwise viewed
from one side, then it's counter-clockwise from the other.

Here, then, is a simpler orientation test, built to Corkum's
specification. The arguments are a pointer to an array of coordinates
arranged (x0, y0, x1, y1, ..., xn, yn), and a count of vertices.  The
return value is 0 is the points are passed clockwise, 1 if counter-clockwise
and -1 if no determination can be made.  This works only for simple polygons.

Isclockwise(float *pv, int nv){
	float *p1, *p2, *endp=pv+2*nv;
	float area=0;	/* acually twice the area */
	for(p1=pv, p2=endp-1; p1!=endp; p2=p1, p1+=2)
		area+=(p2[0]-p1[0])*(p2[1]+p1[1]);
	return area<0 ? 1 : area>2 ? 0 : -1;
}