How to determine if a list of polygon points are in clockwise order?

Question

Having a list of points, how do I find if they are in clockwise order?

For example:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

would say that it is anti-clockwise (counter-clockwise for some people).

Answer 1

Start at one of the vertices, and compute the angle subtended by each side.

The first and the last will be zero (so skip those); for the rest, the sine of the angle will be given by the cross product of the normalizations to unit length of (point[n]-point[0]) and (point[n-1]-point[0]).

If the sum of the values is positive, then your polygon is drawn in the anti-clockwise sense.

Answer 2

find the center of mass of these points.

suppose there are lines from this point to your points.

find the angle between two lines for line0 line1

than do it for line1 and line2

...

...

if this angle is monotonically increasing than it is counterclockwise ,

else if monotonically decreasing it is clockwise

else (it is not monotonical)

you cant decide, so it is not wise

Answer 3

Some of the suggested methods will fail in the case of a non-convex polygon, such as a crescent. Here's a simple one that will work with non-convex polygons (it'll even work with a self-intersecting polygon like a figure-eight, telling you whether it's mostly clockwise).

Sum over the edges, (x2-x1)(y2+y1). If the result is positive the curve is clockwise, if it's negative the curve is counter-clockwise. (The result is twice the enclosed area, with a +/- convention.)

point[0] = (5,0)   edge[0]: (6-5)(4+0) =   4
point[1] = (6,4)   edge[1]: (4-6)(5+4) = -18
point[2] = (4,5)   edge[2]: (1-4)(5+5) = -30
point[3] = (1,5)   edge[3]: (1-1)(0+5) =   0
point[4] = (1,0)   edge[4]: (5-1)(0+0) =   0
                                         ---
                                         -44  counter-clockwise

Answer 4

Because the cross product measures the degree of perpindicularness of two vectors... If you imagine that each edge of your polygon is a vector in the x-y plane of a 3-d xyz space, then the cross product of two successive edges would be a vector in the z-direction (if the second segment is clockwise) or in the minus z-direction (for counter-clockwise)

so for each vertex (point) of the polygon, calculate the cross-product magnitude of the two adjoining edges...

using your data:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

Say vertex A(point[0]) is between

• edge Point[4]->Point[0] is edge A or vector (1-5, 0) = (-4, 0)
• edge Point[0]->Point[1] is edge B or vector (6-5, 4) = ( 1, 4)

then it's cross product is the determinent of following matrix

    i    j    k
   a1   a2    0
   b1   b2    0

or...

  i    j    k 
 -4    0    0
  1    4    0

since all cross-producst are perpindicular to the plane of two vectors being multiplied, this will only have a k-component, (z-axis) and it's value is a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16 The magnitude of this value is a measure of the sine of the angle between the 2 original vectors, times the product of the magnitudes of the 2 vectors.. So you need to divide it by the product of the magnitudes of the two vectors

|A| * |B|    = -16 / (4  * Sqrt(17))

(no need to take arcsine all we will care about is whether sign turns out positive or negative)

do this for each of the other 4 points, and add up the values.

If final sum is positive, you went clockwise, negative, counterclockwise

Answer 5

Find the vertex with smallest y (and largest x if there are ties). Let the vertex be A and the next vertices in the list be B and C. Now compute the sign of the cross product of AB and AC. See this.