Quickhull3d

Computes the convex hull of a set of three dimensional points.

The algorithm is a three dimensional implementation of Quickhull, as described in Barber, Dobkin, and Huhdanpaa, ``The Quickhull Algorithm for Convex Hulls'' (ACM Transactions on Mathematical Software, Vol. 22, No. 4, December 1996), and has a complexity of O(n log(n)) with respect to the number of points. A well-known C implementation of Quickhull that works for arbitrary dimensions is provided by qhull.

Download

Quickhull3d is now in central so just add the dependency:

        ...
                <dependency>
                        <groupId>com.github.quickhull3d</groupId>
                        <artifactId>quickhull3d</artifactId>
                        <version>1.0.0</version>
                </dependency>
                ...

Usage

A hull is constructed by providing a set of points to either a constructor or a build(Point3d[]) method. After the hull is built, its vertices and faces can be retrieved using getVertices() and getFaces(). A typical usage might look like this:

public static void main(String[] args) {
    // x y z coordinates of 6 points
    Point3d[] points = new Point3d[]{
        new Point3d(0.0, 0.0, 0.0),
        new Point3d(1.0, 0.5, 0.0),
        new Point3d(2.0, 0.0, 0.0),
        new Point3d(0.5, 0.5, 0.5),
        new Point3d(0.0, 0.0, 2.0),
        new Point3d(0.1, 0.2, 0.3),
        new Point3d(0.0, 2.0, 0.0),
    };
 
    QuickHull3D hull = new QuickHull3D();
    hull.build(points);
 
    System.out.println("Vertices:");
    Point3d[] vertices = hull.getVertices();
    for (int i = 0; i < vertices.length; i++) {
        Point3d pnt = vertices[i];
        System.out.println(pnt.x + " " + pnt.y + " " + pnt.z);
    }
 
    System.out.println("Faces:");
    int[][] faceIndices = hull.getFaces();
    for (int i = 0; i < vertices.length; i++) {
        for (int k = 0; k < faceIndices[i].length; k++) {
            System.out.print(faceIndices[i][k] + " ");
        }
        System.out.println("");
    }
}

As a convenience, there are also build(double[]) and getVertices(double[]) methods which pass point information using an array of doubles.

Robustness

Because this algorithm uses floating point arithmetic, it is potentially vulnerable to errors arising from numerical imprecision. We address this problem in the same way as qhull, by merging faces whose edges are not clearly convex. A face is convex if its edges are convex, and an edge is convex if the centroid of each adjacent plane is clearly below the plane of the other face. The centroid is considered below a plane if its distance to the plane is less than the negative of a getDistanceTolerance(). This tolerance represents the smallest distance that can be reliably computed within the available numeric precision. It is normally computed automatically from the point data, although an application may setExplicitDistanceTolerance set this tolerance explicitly.

Numerical problems are more likely to arise in situations where data points lie on or within the faces or edges of the convex hull. We have tested QuickHull3D for such situations by computing the convex hull of a random point set, then adding additional randomly chosen points which lie very close to the hull vertices and edges, and computing the convex hull again. The hull is deemed correct if check returns true. These tests have been successful for a large number of trials and so we are confident that QuickHull3D is reasonably robust.

Merged Faces

The merging of faces means that the faces returned by QuickHull3D may be convex polygons instead of triangles. If triangles are desired, the application may triangulate the faces, but it should be noted that this may result in triangles which are very small or thin and hence difficult to perform reliable convexity tests on. In other words, triangulating a merged face is likely to restore the numerical problems which the merging process removed. Hence is it possible that, after triangulation, @link #check check will fail (the same behavior is observed with triangulated output from qhull).

Degenerate Input