Package net.imglib2.mesh.alg.hull

Class ConvexHull

  • public class ConvexHull
extends Object
    This quickhull implementation is based on the paper "The Quickhull Algorithm for Convex Hulls" by Barber, Dobkin and Huhdanpaa (http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf). The computation of the initial simplex is inspired by John Lloyd's quickhull implementation (http://www.cs.ubc.ca/~lloyd/java/quickhull3d.html).
    Author:
    Tim-Oliver Buchholz (University of Konstanz)

    • Constructor Detail

      • ConvexHull

        public ConvexHull()

    • Method Detail

      • calculate

        public static NaiveDoubleMesh calculate​(Mesh input)
        Computes the convex hull of a Mesh
        Parameters:
        input - the input Mesh
        Returns:
        the convex hull of input
        Implementation Note:
        op names="geom.convexHull"

      • calculateEpsilon

        public static double calculateEpsilon​(Mesh input)
        Computes the tolerance (epsilon) of the Mesh.

        The convex hull algorithm implemented is susceptible to errors from the numerical imprecision of floating point arithmetic. In John Lloyd's quickhull implementation, which our implementation follows, these errors usually arise in the form of nonconvex edges, which the quickhull algorithm merges. Given two faces joined by an edge, the edge is considered nonconvex if the centroid of either face is "sufficiently below" the plane of the other face. "Sufficiently below", in this case, means greater than the tolerance, which is computed from the point list.

        Parameters:
        input - the input Mesh
        Returns:
        the epsilon, or tolerance, of the Mesh as computed by the algorithm
        Implementation Note:
        op names='geom.convexHullEpsilon'

      • lastEpsilon

        public static double lastEpsilon()
        Returns the epsilon value of the last computed convex hull.
        Returns:
        the epsilon value of the last computed convex hull.