[GIS] Testing if Geometry is convex using JTS

geometryjavajts-topology-suite

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.

Best Answer

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.

Related Question