[graphics] clockwise or counter-clockwise 2d polygons

[Brent Thomas Corkum]

Archive-name: clockwise-polygon/22-Oct-90
Original-posting-by: corkum at csri.toronto.edu (Brent Thomas Corkum)
Original-subject: clockwise or counter-clockwise 2d polygons
Reposted-by: emv at math.lsa.umich.edu (Edward Vielmetti)

[Reposted from comp.graphics.
Comments on this service to emv at 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 at 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 at csri.toronto.edu or
corkum at 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);
}