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

Question

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, (x₂ − x₁)(y₂ + y₁). 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

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

---

References:

• How do I find the orientation of a simple polygon? in Frequently Asked Questions: comp.graphics.algorithms.

• Curve orientation at Wikipedia.

I'm going to throw out another solution because it's straightforward and not mathematically intensive - it just uses basic algebra. Calculate the signed area of the polygon. If it's negative the points are in clockwise order, if it's positive they are counterclockwise. (This is very similar to Beta's solution.)

Calculate the signed area: A = 1/2 * (x₁*y₂ - x₂*y₁ + x₂*y₃ - x₃*y₂ + ... + x_n*y₁ - x₁*y_n)

Or in pseudo-code:

signedArea = 0
for each point in points:
    x1 = point[0]
    y1 = point[1]
    if point is last point
        x2 = firstPoint[0]
        y2 = firstPoint[1]
    else
        x2 = nextPoint[0]
        y2 = nextPoint[1]
    end if

    signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2

Note that if you are only checking the ordering, you don't need to bother dividing by 2.

Sources: http://mathworld.wolfram.com/PolygonArea.html

The cross product measures the degree of perpendicular-ness of two vectors. Imagine that each edge of your polygon is a vector in the x-y plane of a three-dimensional (3-D) xyz space. Then the cross product of two successive edges is a vector in the z-direction, (positive z-direction if the second segment is clockwise, minus z-direction if it's counter-clockwise). The magnitude of this vector is proportional to the sine of the angle between the two original edges, so it reaches a maximum when they are perpendicular, and tapers off to disappear when the edges are collinear (parallel).

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)

So Label the edges consecutively as
edgeA is the segment from point0 to point1 and
edgeB between point1 to point2
...
edgeE is between point4 and point0.

Then Vertex A (point0) is between
edgeE [From point4 to point0]
edgeA [From point0 to `point1'

These two edges are themselves vectors, whose x and y coordinates can be determined by subtracting the coordinates of their start and end points:

edgeE = point0 - point4 = (1, 0) - (5, 0) = (-4, 0) and
edgeA = point1 - point0 = (6, 4) - (1, 0) = (5, 4) and

And the cross product of these two adjoining edges is calculated using the determinant of the following matrix, which is constructed by putting the coordinates of the two vectors below the symbols representing the three coordinate axis (i, j, & k). The third (zero)-valued coordinate is there because the cross product concept is a 3-D construct, and so we extend these 2-D vectors into 3-D in order to apply the cross-product:

 i    j    k 
-4    0    0
 1    4    0    

Given that all cross-products produce a vector perpendicular to the plane of two vectors being multiplied, the determinant of the matrix above only has a k, (or z-axis) component.
The formula for calculating the magnitude of the k or z-axis component is
a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16

The magnitude of this value (-16), is a measure of the sine of the angle between the 2 original vectors, multiplied by the product of the magnitudes of the 2 vectors.
Actually, another formula for its value is
A X B (Cross Product) = |A| * |B| * sin(AB).

So, to get back to just a measure of the angle you need to divide this value, (-16), by the product of the magnitudes of the two vectors.

|A| * |B| = 4 * Sqrt(17) = 16.4924...

So the measure of sin(AB) = -16 / 16.4924 = -.97014...

This is a measure of whether the next segment after the vertex has bent to the left or right, and by how much. There is no need to take arc-sine. All we will care about is its magnitude, and of course its sign (positive or negative)!

Do this for each of the other 4 points around the closed path, and add up the values from this calculation at each vertex..

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

Here is a simple C# implementation of the algorithm based on this answer.

Let's assume that we have a Vector type having X and Y properties of type double.

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count];
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

% is the modulo or remainder operator performing the modulo operation which (according to Wikipedia) finds the remainder after division of one number by another.

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.

An implementation of Sean's answer in JavaScript:

function calcArea(poly) {
    if(!poly || poly.length < 3) return null;
    let end = poly.length - 1;
    let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1];
    for(let i=0; i<end; ++i) {
        const n=i+1;
        sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1];
    }
    return sum;
}

function isClockwise(poly) {
    return calcArea(poly) > 0;
}

let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]];

console.log(isClockwise(poly));

let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]];

console.log(isClockwise(poly2));

Pretty sure this is right. It seems to be working :-)

Those polygons look like this, if you're wondering: