You are here

Determining whether or not a polygon (2D) has its vertices ordered clockwise or counterclockwise(T)

Org link: http://debian.fmi.uni-sofia.bg/~sergei/cgsr/docs/clockwise.htm

 


Determining whether or not a polygon (2D) has its
vertices ordered clockwise or counterclockwise
Written by Paul Bourke
March 1998

The following describes a method for determining whether or not
a polygon has its vertices ordered clockwise or anticlockwise.
As a consequence the test can also be used to determine whether or
not a polygon is concave or convex.
A polygon will be assumed to be described by N vertices, ordered

(x0,y0), (x1,y1),
(x2,y2), . . . (xn-1,yn-1)

A convenient definition of clockwise is based on considerations of
the cross product between adjacent edges. If the crossproduct is
positive then it rises above the plane (z axis up out of the plane)
and if negative then the cross product is into the plane.

 

cross product =
((xi - xi-1),(yi - yi-1))
x
((xi+1 - xi),(yi+1 - yi))

=
(xi - xi-1) * (yi+1 - yi)
- (yi - yi-1) * (xi+1 - xi)

If the polygon is known to be convex then one only has to consider
the cross product between any two adjacent edges. A positive cross
product means we have a counterclockwise polygon. There are some
tests that may need to be done if the polygons may not be "clean".
In particular two vertices must not be coincident and two edges must
not be colinear.

For the more general case where the polygons may be convex, it is
necessary to consider the sign of the cross product between adjacent
edges as one moves around the polygon. If there are more positive
cross products then the overall polygon is ordered counterclockwise.
There are pathological cases to consider here as well, all the edges
cannot be colinear, there must be at least 3 vertices, the polygon
must be simple, that is, it cannot intersect itself or have holes.


Test for concave/convex polygon
A similar argument to the above can be used to determine whether a
polygon is concave or convex.
For a convex polygon all the cross products of adjacent edges will
be the same sign, a concave polygon will have a mixture of cross
product signs.

 

Source Code
Example and test program for testing
whether a polygon is ordered clockwise or counterclockwise.
For MICROSOFT WINDOWS, contributed by G. Adam Stanislav.

C function by Paul Bourke

/*
Return the clockwise status of a curve, clockwise or counterclockwise
n vertices making up curve p
return 0 for incomputables eg: colinear points
CLOCKWISE == 1
COUNTERCLOCKWISE == -1
It is assumed that
- the polygon is closed
- the last point is not repeated.
- the polygon is simple (does not intersect itself or have holes)
*/
int ClockWise(XY *p,int n)
{
int i,j,k;
int count = 0;
double z;
if (n < 3)
return(0);
for (i=0;i<n;i++) {
j = (i + 1) % n;
k = (i + 2) % n;
z = (p[j].x - p[i].x) * (p[k].y - p[j].y);
z -= (p[j].y - p[i].y) * (p[k].x - p[j].x);
if (z < 0)
count--;
else if (z > 0)
count++;
}
if (count > 0)
return(COUNTERCLOCKWISE);
else if (count < 0)
return(CLOCKWISE);
else
return(0);
}

Example and test program for testing
whether a polygon is convex or concave.
For MICROSOFT WINDOWS, contributed by G. Adam Stanislav.

 

/*
Return whether a polygon in 2D is concave or convex
return 0 for incomputables eg: colinear points
CONVEX == 1
CONCAVE == -1
It is assumed that the polygon is simple
(does not intersect itself or have holes)
*/
int Convex(XY *p,int n)
{
int i,j,k;
int flag = 0;
double z;
if (n < 3)
return(0);
for (i=0;i<n;i++) {
j = (i + 1) % n;
k = (i + 2) % n;
z = (p[j].x - p[i].x) * (p[k].y - p[j].y);
z -= (p[j].y - p[i].y) * (p[k].x - p[j].x);
if (z < 0)
flag |= 1;
else if (z > 0)
flag |= 2;
if (flag == 3)
return(CONCAVE);
}
if (flag != 0)
return(CONVEX);
else
return(0);
}

Comments

#include "stdafx.h"
#include "stdio.h"
typedef struct tagPoint
{
double x;
double y;
}FPoint;
double Area(FPoint *pArray,int NumPoint)
{
if(NumPoint<3)return 0;

double sum = 0;
int m = 1;
for(;;)
{
if(NumPoint < 3)break;
FPoint r1;
r1.x = pArray[m].x - pArray[0].x;
r1.y = pArray[m].y - pArray[0].y;
FPoint r2;
r2.x = pArray[m+1].x - pArray[m].x;
r2.y = pArray[m+1].y - pArray[m].y;
sum += (r1.x * r2.y - r2.x * r1.y);
m++;
NumPoint --;
}
double result = (sum>0)?(sum/2.):(-sum/2.);
return result;
}
//test
void main()
{
FPoint pArray1[4]={{1,1},{1,2},{2,2},{2,1}};
FPoint pArray2[5]={{0,0},{0,2},{2,2},{1,1},{2,0}};
FPoint pArray3[9]={{0,0},{2,0},{2,1},{0,1},{0,2},{-2,0},{-1,0},{-1,-1},{0,-1}};
printf("Area1 = %f\n",Area(pArray1,4));
printf("Area2 = %f\n",Area(pArray2,5));
printf("Area3 = %f\n",Area(pArray3,9));
}