Detect if a set of points in an array that are the vertices of a complex polygon were defined in a clockwise or counterclockwise order?

Question

EDIT: I updated the program with the answer and it works great!

I am making a program (feel free to try it out) that lets users draw polygons which it then triangulates. They can click to add vertices and hit enter to triangulate. Anyways, the algorithm works fine as long as I tell it if the points were drawn in a clockwise or counterclockwise fashion (right now I have it set only to work with clockwise polygons). I have been trying to figure this out for days, but have no idea how to determine whether the points are clockwise or counterclockwise. Try drawing shapes with the program mentioned earlier to get a better idea, you can experience what I am talking about better than I can try to explain it.

Here is how the points are defined:

function Point(x, y) {
    this.x = x;
    this.y = y;
}

var vertices = [];

// Called on click
function addPoint(mouseX, mouseY) {
    vertices.push(new Point(mouseX, mouseY));
}

Here is an image of a clockwise polygon:

Here is an image of a counterclockwise polygon:

If you could help me figure out how to determine the "clockwise-ness" of the points, I would be very grateful!

Answer 1

Compute the polygon area using the shoelace formula, but without the absolute value sign. If the result is positive, the points are ordered counterclockwise, and if negative - clockwise.

function polygonArea() { 
    var area = 0;
    for (var i = 0; i < vertices.length; i++) {
        j = (i + 1) % vertices.length;
        area += vertices[i].x * vertices[j].y;
        area -= vertices[j].x * vertices[i].y;
    }
    return area / 2;
}
var clockwise = polygonArea() > 0;

Answer 2

A general idea would be to take a look at the convex hull of your polygone and guess the orientation from there. However, I think that you do not need to build the whole hull to find the orientation, but just one segment belonging to it.

So:

• Find two points of your polygones so that all the other points are on one side of this line.
• If all the points are on the left (just check one of the points), it's counterclockwise. If they are on the right, it's clockwise.

Example:

On the top figure: 4-5 let the figure on the right, 5-11 let the figure on the right, ... On the bottom figure: 6-7 let the figure on the left, 7-14 let the figure on the left, ...

Warning: While "walking" on your polygon, do not restart the numeration, otherwise it will be wrong. On the top figure, 4-(n-1) let the figure on the left!

Answer 3

In case someone is using three.js the ShapeUtils comes with an inbuilt isClockWise method which internally uses the area method to determine the sign of the calculated area.

isClockWise: function ( pts ) {

    return ShapeUtils.area( pts ) < 0;

}

The ShapeUtils.isClockWise Method can be found here.

area: function ( contour ) {

    var n = contour.length;
    var a = 0.0;

    for ( var p = n - 1, q = 0; q < n; p = q ++ ) {

        a += contour[ p ].x * contour[ q ].y - contour[ q ].x * contour[ p ].y;

    }

    return a * 0.5;

},

The ShapeUtils.area Method can be found here.