3

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.

  • Do you can PostGIS in Java? – Samane Aug 9 '15 at 9:44
  • I'm not using a PostGIS database, no, so I can't do ST_IsConvex or anything like that (if it exists). I don't have GeoTools on my classpath for this project, does it support it? – Wouter Lievens Aug 9 '15 at 20:42
  • If you do not have PostGIS database, so you cant use it commands! – Samane Aug 10 '15 at 4:46
  • I'm aware of that. – Wouter Lievens Aug 10 '15 at 5:45
5

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

The polygon is convex if each 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.

  • 1
    I think that this method may give false negatives. Take a polygon POLYGON (( 0 0, 0 -5, 5 -5, 10 -5, 10 0, 0 0 )). It is convex but not equal to its convex hull which is POLYGON (( 0 0, 0 -5, 10 -5, 10 0, 0 0 )). Notice the intermittent vertex at (5 -5). One should compare the geometry after it has been generalized with a tolerance of zero with its convex hull. – user30184 Aug 10 '15 at 7:31
  • D'oh! You're right. I added a simpler answer above. – Rob Skelly Aug 10 '15 at 15:34
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;
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.