Testing if Geometry is convex using JTS?

Question

I'm using the Java Topology Suite and I'd like to efficiently check if a Geometry (a Polygon in fact) is convex or not.

I currently do if (geometry.convexHull().equals(geometry)) but obivously that is ... suboptimal :)

I could implement it myself with the early-interruption condition on the gift-wrapping algorithm, but I can't imagine that this isn't implemented in JTS already.

Answer 1

OK, my original answer was wrong (see user30184's comment). Here's another:

The polygon is convex if each interior angle is 180 degrees or less. You can check this in O(n) time, iterating over the triples of points in the exterior ring and checking the sign of the determinant.

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.LinearRing;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;


public class Test {

    public static void main(String[] args) throws ParseException {
        WKTReader r = new WKTReader();
        Polygon notConvex = (Polygon) r.read("POLYGON((0 0, 5 0, 5 5, 2.5 2.5, 0 5, 0 0))");
        Polygon convex = (Polygon) r.read("POLYGON((0 0, 5 0, 5 5, 0 5, 0 0))");
        System.out.println(isConvex(notConvex));
        System.out.println(isConvex(convex));
    }

    public static boolean isConvex(Polygon p) {
        LinearRing r = (LinearRing) p.getExteriorRing();
        int sign = 0;
        for(int i = 1; i < r.getNumPoints(); ++i) {
            Coordinate c0 = r.getCoordinateN(i == 0 ? r.getNumPoints() - 1 : i - 1);
            Coordinate c1 = r.getCoordinateN(i);
            Coordinate c2 = r.getCoordinateN(i == r.getNumPoints() - 1 ? 0 : i + 1);
            double dx1 = c1.x - c0.x;
            double dy1 = c1.y - c0.y;
            double dx2 = c2.x - c1.x;
            double dy2 = c2.y - c2.y;
            double z = dx1 * dy2 - dy1 * dx2;
            int s = z >= 0.0 ? 1 : -1;
            if(sign == 0) {
                sign = s; 
            } else if(sign != s) {
                return false;
            }
        }
        return true;
    }
}

}

Original Answer:

You'd want to check whether the convex hull of the geometry is equal to the outer ring of the geometry (assuming it's contiguous), not the entire geometry. The Graham scan algorithm (used by JTS) is O(n log n), and the checking whether two rings are identical is O(n) in the number of points in the ring. That seems pretty fast to (non-geometer) me.

Answer 2

I am not sure if this is a more efficient way but you could also compare the area of the input polygon to the area of the convex hull of the same polygon.

The area of the convex hull of a concave polygon is always bigger than the area of the concave polygon itself.

Simple method:

public static boolean isConvexPolygon(Polygon p){
    Polygon convexHull = (Polygon) p.convexHull();
    // compare area of input polygon to area of the convex hull
    if(convexHull.getArea() > p.getArea()){
        return false;
    } else {
        return true;
    }
}