AutSoft Logo

Openlayers battles - Is this polygon convex or not?


Once upon a time there was a request from the customer to be able to draw polygons on a map. Later there were more and more feature requests to transfom this polygon editor into a swiss army knife. One of them was to prevent users to draw concave polygons on the map.

This would be pretty easy - I thought - if it were only a wonderful Openlayers function e.g polygon.isConvex(). But it wasn't, or at least I could find it in version 2.13.1.
I was searching the internet, trying to find the simplest solution, because I was sure there is a more elegant and shorter solution than hacking with angles.

Finally StackOverflow came to my help (as always :). In this thread I found the most suitable algorithm for my need.

A polygon is a set of points in a list where the consecutive points form the boundary. It is much easier to figure out whether a polygon is convex or not (and you don't have to calculate any angles, either):

For each consecutive pair of edges of the polygon (each triplet of points), compute the z-component of the cross product of the vectors defined by the edges pointing towards the points in increasing order. Take the cross product of these vectors:

given p[k], p[k+1], p[k+2] each with coordinates x, y:
 dx1 = x[k+1]-x[k]
 dy1 = y[k+1]-y[k]
 dx2 = x[k+2]-x[k+1]
 dy2 = y[k+2]-y[k+1]
 zcrossproduct = dx1*dy2 - dy1*dx2

The polygon is convex if the z-components of the cross products are either all positive or all negative. Otherwise the polygon is nonconvex.

If there are N points, make sure you calculate N cross products, e.g. be sure to use the triplets (p[N-2],p[N-1],p[0]) and (p[N-1],p[0],p[1]).

You can checkout my Javascript implementation of this algorithm:

function calculateAllCrossProduct(points) {
    var lastSign = null;

    for (var i = 2; i < points.length; i++) {
        //calculate crossproduct from 3 consecutive points
        var crossproduct = calculateCrossProduct(points[i - 2], points[i - 1], points[i]);
		console.log(i + ". crossproduct from ("+ points[i - 2].x +" "+points[i - 1].x +" "+points[i].x +"): " + crossproduct);
        var currentSign = Math.sign(crossproduct);
        if (lastSign == null) {
        	//last sign init
        	lastSign = currentSign;

        console.log("Last sign: " + lastSign + " current sign: "+currentSign);
        var checkResult = checkCrossProductSign(lastSign, currentSign);
        if (checkResult == false) {
            //different sign in cross products,no need to check the remaining points --> concave polygon --> return function
            return false;
        lastSign = currentSign;

    //first point must check between second and last point, this is the last 3 points that can break convexity
    var crossproductFirstPoint = calculateCrossProduct(points[points.length - 2], points[0], points[1]);
    console.log("cross product first point: ", crossproductFirstPoint);
    return checkCrossProductSign(lastSign, Math.sign(crossproductFirstPoint));

function checkCrossProductSign(lastSign, newSign) {
    if (lastSign !== newSign) {
        //checked sign differs from the previous one --> concave polygon
        return false;
    return true;

function calculateCrossProduct(p1, p2, p3) {

    var dx1 = p2.x - p1.x;
    var dy1 = p2.y - p1.y;
    var dx2 = p3.x - p2.x;
    var dy2 = p3.y - p2.y;

    var zcrossproduct = dx1 * dy2 - dy1 * dx2;
    return zcrossproduct;

function isPolygonConvex(points) {    
    return calculateAllCrossProduct(points);

var pointsConvexPolygon = [{"x":2117708.7303958,"y":6024264.0003844},{"x":2118950.8321053,"y":6026690.8760321},{"x":2121110.178154,"y":6024187.5633561},{"x":2119361.6811323,"y":6023432.7477018},{"x":2117708.7303958,"y":6024264.0003844}];
var pointsConcavePolygon = [{"x":2119934.9588443,"y":6024579.3031259},{"x":2118950.8321053,"y":6026690.8760321},{"x":2121110.178154,"y":6024187.5633561},{"x":2119361.6811323,"y":6023432.7477018},{"x":2119934.9588443,"y":6024579.3031259}];


Follow us on social media

Ezek is érdekelhetnek

magnifiercross linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram