Java commons-math Issue forming and extracting verices of ConvexHull2D

Question

I am working on ConvexHull problem and I need to identify vertices of a convex hull. I am using Apache commons-math's - ConvexHull2D. Here is what I have so far

public static void main(String[] args) {

        Vector2D v1 = new Vector2D(1, 3);
        Vector2D v2 = new Vector2D(-1, 3);
        Vector2D v3 = new Vector2D(0, -2);
        Vector2D v4 = new Vector2D(-1, -3);
        Vector2D v5 = new Vector2D(-12, -13);
        Vector2D v6 = new Vector2D(-10, -30);

        Vector2D[] vertices = {v1,v2,v3,v4,v5,v6};
        double tolerance = 1;

        ConvexHull2D ch = new ConvexHull2D(vertices, tolerance);
        vertices =ch.getVertices();

        System.out.println(vertices);

    }

But with this code I am seeing this exception

Exception in thread "main" org.apache.commons.math3.exception.MathIllegalArgumentException: vertices do not form a convex hull in CCW winding
    at org.apache.commons.math3.geometry.euclidean.twod.hull.ConvexHull2D.<init>(ConvexHull2D.java:69)
    at run_ootb_templates.LongitudeLatitudeTest.main(LongitudeLatitudeTest.java:22)

My understanding of the convex hull is any 3 points in space are capable of forming a convex hull and any additional point other than these 3 can be accommodated in this boundary of convex hull.

Any help towards resolution is appreciated, also if any sample datasets so that I can understand this

Answer 1

The documentation for this area of Apache commons-math doesn't seem very good, but from looking at the source code it's clear that ConvexHull2D requires the vertices to already form a convex polygon. This is enforced by checking for a consistent turning direction as you move along the boundary. Your points don't form a convex polygon, hence the exception.

Instead what you want is to use an implementation of the ConvexHullGenerator2D interface, e.g. MonotoneChain, to build a ConvexHull2D via the generate(Collection<Vector2D> points) method.