Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!atc
From: atc@cs.utexas.edu (Alvin T. Campbell III)
Newsgroups: comp.graphics
Subject: Re: Computational geometry
Message-ID: <5397@cs.utexas.edu>
Date: 29 Apr 89 20:41:51 GMT
References: <2053@incas.UUCP>
Organization: U. Texas CS Dept., Austin, Texas
Lines: 105

In article <2053@incas.UUCP> mdoerr@incas.UUCP (Michael Doerr) writes:
>
>	How does one determine _reliabely_ (!!!) the winding sense (clockwise
>	or counter-clockwise) of the sides of an arbitrary polygon?
>
>I've come up with the following algorithm and would like to know whether
>it is correct:
>	[ALGORITHM DELETED FOR SPACE CONSIDERATIONS}


I recently had to solve the winding-sense problem myself.
I am glad to see other people have had to deal with it as well.

Michael's algorithm looks as if it will work, but it will not
be very fast. The method I devised is very simple and fast.
I believe it to be robust.  My solution is described below, 
along with source code in C.

Now for the method.  Assume that we have a polygon with n 
vertices, numbered v1, v2, ..., vn.  First, we find the vertex,
vtop, with the largest y-coordinate.  The angle of the polygon
at this vertex is guaranteed to be convex.  Now we take the 
cross-product of the vectors (vaft, vtop) and (vtop, vbef),
where vaft is the vertex following vtop, and vbef is the vertex
preceding vtop. If the cross-product is negative, the vertices
are counter-clockwise.  Otherwise, the vertices are clockwise.

/********************************CUT HERE *****************************/
/*
	file:		clockwise.c
	description:	determine if verts of a polygon are specified in 
			clockwise order
	author:		A. T. Campbell
	date:		February 8, 1989
	routines:	clockwise()
*/

#include <math.h>

#ifndef lint
static char 	sccsid[] = "%W% %G%";	/* SCCS info */
#endif lint

/******************************************************************************/

/* constants */
#define FALSE 	0
#define TRUE	1

/******************************************************************************/

int
clockwise(n, v)					/* decide if vertices are
						   clockwise */
int	n;					/* number of vertices */
float	v[][2];					/* list of vertices */
{
	float	*top; 				/* topmost point */
	float	*bef; 				/* point before topmost */
	float	*aft;				/* point after topmost */
	float	topy;				/* highest y coordinate */
	float	topaft[2];			/* vector from top vert to next */
	float	topbef[2];			/* vector from top vert to previous */
	float	prod;				/* dot product */
	int	i;				/* loop control */
	int	aftind;				/* index of pnt after top */
	int	befind;				/* index of pnt before top */
	int	topind;				/* index of topmost pnt */

	if (n < 3) return(TRUE);

	/* find topmost point */
	topy = -MAXFLOAT;
	for (i = 0; i < n; i++)
		if (v[i][1] > topy) {
			topy = v[i][1];
			topind = i;
		}

	/* find indices before and after */
	befind = (topind > 0)? topind - 1 : n - 1;
	aftind = (topind < n-1)? topind + 1 : 0;

	top = &(v[topind][0]);
	bef = &(v[befind][0]);
	aft = &(v[aftind][0]);

	/* calculate vectors */
	topaft[0] = aft[0] - top[0];
	topaft[1] = aft[1] - top[1];
	topbef[0] = bef[0] - top[0];
	topbef[1] = bef[1] - top[1];

	/* cross-multiply vectors */
	prod = topbef[0] * topaft[1] - topbef[1] * topaft[0];

	/* if cross-product is positive, then clockwise */
	return((prod >= 0.)? TRUE: FALSE);
}

/******************************************************************************/
-- 
				A. T. Campbell, III
				CS Department, University of Texas
				atc@cs.utexas.edu