corkum@csri.toronto.edu (Brent Thomas Corkum) (10/23/90)
Archive-name: clockwise-polygon/22-Oct-90
Original-posting-by: corkum@csri.toronto.edu (Brent Thomas Corkum)
Original-subject: clockwise or counter-clockwise 2d polygons
Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti)
[Reposted from comp.graphics.
Comments on this service to emv@math.lsa.umich.edu (Edward Vielmetti).]
This routine and sample program computes whether a 2D polygon is clockwise
or counter-clockwise. The function takes vertices passed in an array
(x1,y1,x2,y2,...xn,yn where n=#vertices) and the number of vertices.
Of course for a 3D polygon, clockwise or counter-clockwise depends
on which way you look at it.
Brent Corkum
corkum@csri.toronto.edu
This function is also available via anonymous ftp at
boulder.civ.toronto.edu (128.100.14.11)
int the
pub/CCW_OR_CW
directory.
P.S. Feel free to use and distribute this function. Any use or misuse
of this function is the responsibility of the user. If you
use this function, the header must remain in place to acknowledge
my contribution.
/*---------------------------cut here--------------------------------*/
#include <stdio.h>
#include <math.h>
#define ABS(x) ((x)<0.0 ? -(x) : (x))
/*
compile with:
cc <file.c> -lm
*/
main()
{
float pl[100];
int numv,i,flag;
printf("Enter #numvertices: ");
scanf("%d",&numv);
for(i=1;i<=numv;++i){
printf("Enter Vertex %d: ",i);
scanf("%f%f",&pl[2*(i-1)],&pl[2*(i-1)+1]);
}
flag=Isclockwise(pl,numv);
if(flag==1) printf("polygon is clockwise\n");
else if(flag==0) printf("polygon is counter-clockwise\n");
else printf("invalid polygon\n");
}
/*
Function by :
Brent Corkum
Data Visualization Lab
Civil Engineering
University of Toronto
Toronto Ontario Canada
corkum@csri.toronto.edu or
corkum@boulder.civ.toronto.edu (128.100.14.11)
That determines whether a 2d polygons vertices are orderred clockwise
or counter-clockwise. The polygon is passed as an array of vertices
(x1,y1,x2,y2,...,xn,yn where n=numv=#vertices or edges in the closed polygon).
The function returns 1 if the polygon is clockwise and 0 if the polygon
is counterclockwise. The function returns -1 if numv<3.
*/
int Isclockwise(pl,numv)
float *pl;
int numv;
{
int index,pindex,aindex,i,flag;
float maxv,eps,dx,dy,adx,ady,xi,yi,xj,yj,xh,yh,xtest,trend;
if(numv<3)return(-1);
/* calculate an epsilon for floating point comparisons */
eps = 1e-5 * ABS(pl[0]);
if(eps<1e-5)eps=1e-5;
/* filter out last point if equal to first point */
if(pl[0]==pl[2*(numv-1)] && pl[1]==pl[2*(numv-1)+1])--numv;
/* compute the vertex with the minimum x value, if there's more than one
compute the vertex that has the minimum x and y value (min vertex=P) */
index=0;
for(i=1;i<numv;++i){
dx=pl[2*i]-pl[2*index];dy=pl[2*i+1]-pl[2*index+1];
adx = ABS(dx); ady = ABS(dy);
if(adx>eps){
if(dx<0.0)index=i;
}
else{
if(dy<0.0)index=i;
}
}
/* compute the previous vertex, making sure that the previous vertex does
not equal the min vertex (Pp)*/
pindex=index;flag=1;
do{
--pindex;
if(pindex<0)pindex=numv-1;
dx=pl[2*pindex]-pl[2*index];dy=pl[2*pindex+1]-pl[2*index+1];
adx = ABS(dx); ady = ABS(dy);
if(adx>eps || ady>eps)flag=0;
else if(pindex==index)flag=0;
}while(flag);
/* compute the vertex coming after the min vertex, making sure that it
doesn't equal the min vertex (Pa)*/
aindex=index;flag=1;
do{
++aindex;
if(aindex==numv)aindex=0;
dx=pl[2*aindex]-pl[2*index];dy=pl[2*aindex+1]-pl[2*index+1];
adx = ABS(dx); ady = ABS(dy);
if(adx>eps || ady>eps)flag=0;
else if(aindex==index)flag=0;
}while(flag);
/* compute whether angle made by Pp -> P ->Pa is convex or concave,
the angle is measured counterclockwise from Pp->P */
if(aindex != index && pindex != index){
xh = pl[2*pindex] ; yh = pl[2*pindex+1];
xi = pl[2*index] ; yi = pl[2*index+1];
xj = pl[2*aindex] ; yj = pl[2*aindex+1];
/* compute azimuth of Pp->P */
dx = xi-xh ; dy = yi-yh;
if(dx==0.0 && dy==0.0) trend = 0.0;
else{
trend = atan2(dx,dy);
if(trend < 0.0) trend += 6.283185308; /* += 2*PI */
}
/* rotate x value of Pp->P to positive y axis(x=0) and x of
P-Pa by same angle */
dx = xj-xi ; dy = yj-yi;
xtest = dx*cos(trend) - dy*sin(trend);
/* if xtest is >= 0.0 then you know that the angle between Pp->P and
P->Pa is CONVEX and therefore the polygon is clockwise */
if(xtest>=0.0)return(1);
else return(0);
}
return(-1);
}