public class QuickHull3D extends Object
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 wellknown C implementation of Quickhull that works for arbitrary dimensions is provided by qhull.
A hull is constructed by providing a set of points
to either a constructor or a
build
method. After
the hull is built, its vertices and faces can be retrieved
using getVertices
and getFaces
.
A typical usage might look like this:
// 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 < faceIndices.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
and getVertex
methods which
pass point information using an array of doubles.
distance tolerance
. 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 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.
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, check
will fail (the same
behavior is observed with triangulated output from qhull).
distance tolerance
, an
IllegalArgumentException will be thrown.Modifier and Type  Field and Description 

static double 
AUTOMATIC_TOLERANCE
Specifies that the distance tolerance should be
computed automatically from the input point data.

static int 
CLOCKWISE
Specifies that (on output) vertex indices for a face should be
listed in clockwise order.

static int 
INDEXED_FROM_ONE
Specifies that (on output) the vertex indices for a face should be
numbered starting from 1.

static int 
INDEXED_FROM_ZERO
Specifies that (on output) the vertex indices for a face should be
numbered starting from 0.

static int 
POINT_RELATIVE
Specifies that (on output) the vertex indices for a face should be
numbered with respect to the original input points.

Constructor and Description 

QuickHull3D()
Creates an empty convex hull object.

QuickHull3D(double[] coords)
Creates a convex hull object and initializes it to the convex hull
of a set of points whose coordinates are given by an
array of doubles.

QuickHull3D(Point3d[] points)
Creates a convex hull object and initializes it to the convex hull
of a set of points.

Modifier and Type  Method and Description 

void 
build(double[] coords)
Constructs the convex hull of a set of points whose
coordinates are given by an array of doubles.

void 
build(double[] coords,
int nump)
Constructs the convex hull of a set of points whose
coordinates are given by an array of doubles.

void 
build(Point3d[] points)
Constructs the convex hull of a set of points.

void 
build(Point3d[] points,
int nump)
Constructs the convex hull of a set of points.

boolean 
check(PrintStream ps)
Checks the correctness of the hull using the distance tolerance
returned by
getDistanceTolerance ; see
check(PrintStream,double) for details. 
boolean 
check(PrintStream ps,
double tol)
Checks the correctness of the hull.

boolean 
getDebug()
Returns true if debugging is enabled.

double 
getDistanceTolerance()
Returns the distance tolerance that was used for the most recently
computed hull.

double 
getExplicitDistanceTolerance()
Returns the explicit distance tolerance.

int[][] 
getFaces()
Returns the faces associated with this hull.

int[][] 
getFaces(int indexFlags)
Returns the faces associated with this hull.

int 
getNumFaces()
Returns the number of faces in this hull.

int 
getNumVertices()
Returns the number of vertices in this hull.

int[] 
getVertexPointIndices()
Returns an array specifing the index of each hull vertex
with respect to the original input points.

Point3d[] 
getVertices()
Returns the vertex points in this hull.

int 
getVertices(double[] coords)
Returns the coordinates of the vertex points of this hull.

void 
print(PrintStream ps)
Prints the vertices and faces of this hull to the stream ps.

void 
print(PrintStream ps,
int indexFlags)
Prints the vertices and faces of this hull to the stream ps.

void 
setDebug(boolean enable)
Enables the printing of debugging diagnostics.

void 
setExplicitDistanceTolerance(double tol)
Sets an explicit distance tolerance for convexity tests.

void 
triangulate()
Triangulates any nontriangular hull faces.

public static final int CLOCKWISE
public static final int INDEXED_FROM_ONE
public static final int INDEXED_FROM_ZERO
public static final int POINT_RELATIVE
public static final double AUTOMATIC_TOLERANCE
public QuickHull3D()
public QuickHull3D(double[] coords) throws IllegalArgumentException
coords
 x, y, and z coordinates of each input
point. The length of this array will be three times
the the number of input points.IllegalArgumentException
 the number of input points is less
than four, or the points appear to be coincident, colinear, or
coplanar.public QuickHull3D(Point3d[] points) throws IllegalArgumentException
points
 input points.IllegalArgumentException
 the number of input points is less
than four, or the points appear to be coincident, colinear, or
coplanar.public boolean getDebug()
setDebug(boolean)
public void setDebug(boolean enable)
enable
 if true, enables debuggingpublic double getDistanceTolerance()
setExplicitDistanceTolerance(double)
public void setExplicitDistanceTolerance(double tol)
AUTOMATIC_TOLERANCE
is specified (the default), then the tolerance will be computed
automatically from the point data.tol
 explicit tolerancegetDistanceTolerance()
public double getExplicitDistanceTolerance()
setExplicitDistanceTolerance(double)
public void build(double[] coords) throws IllegalArgumentException
coords
 x, y, and z coordinates of each input
point. The length of this array will be three times
the number of input points.IllegalArgumentException
 the number of input points is less
than four, or the points appear to be coincident, colinear, or
coplanar.public void build(double[] coords, int nump) throws IllegalArgumentException
coords
 x, y, and z coordinates of each input
point. The length of this array must be at least three times
nump
.nump
 number of input pointsIllegalArgumentException
 the number of input points is less
than four or greater than 1/3 the length of coords
,
or the points appear to be coincident, colinear, or
coplanar.public void build(Point3d[] points) throws IllegalArgumentException
points
 input pointsIllegalArgumentException
 the number of input points is less
than four, or the points appear to be coincident, colinear, or
coplanar.public void build(Point3d[] points, int nump) throws IllegalArgumentException
points
 input pointsnump
 number of input pointsIllegalArgumentException
 the number of input points is less
than four or greater then the length of points
, or the
points appear to be coincident, colinear, or coplanar.public void triangulate()
public int getNumVertices()
public Point3d[] getVertices()
getVertices(double[])
,
getFaces()
public int getVertices(double[] coords)
coords
 returns the x, y, z coordinates of each vertex.
This length of this array must be at least three times
the number of vertices.getVertices()
,
getFaces()
public int[] getVertexPointIndices()
public int getNumFaces()
public int[][] getFaces()
Each face is represented by an integer array which gives the
indices of the vertices. These indices are numbered
relative to the
hull vertices, are zerobased,
and are arranged counterclockwise. More control
over the index format can be obtained using
getFaces(indexFlags)
.
getVertices()
,
getFaces(int)
public int[][] getFaces(int indexFlags)
Each face is represented by an integer array which gives the
indices of the vertices. By default, these indices are numbered with
respect to the hull vertices (as opposed to the input points), are
zerobased, and are arranged counterclockwise. However, this
can be changed by setting POINT_RELATIVE
, INDEXED_FROM_ONE
, or
CLOCKWISE
in the indexFlags parameter.
indexFlags
 specifies index characteristics (0 results
in the default)getVertices()
public void print(PrintStream ps)
This is done using the Alias Wavefront .obj file
format, with the vertices printed first (each preceding by
the letter v
), followed by the vertex indices
for each face (each
preceded by the letter f
).
The face indices are numbered with respect to the hull vertices
(as opposed to the input points), with a lowest index of 1, and are
arranged counterclockwise. More control over the index format can
be obtained using
print(ps,indexFlags)
.
ps
 stream used for printingprint(PrintStream,int)
,
getVertices()
,
getFaces()
public void print(PrintStream ps, int indexFlags)
This is done using the Alias Wavefront .obj file format, with
the vertices printed first (each preceding by the letter
v
), followed by the vertex indices for each face (each
preceded by the letter f
).
By default, the face indices are numbered with respect to the
hull vertices (as opposed to the input points), with a lowest index
of 1, and are arranged counterclockwise. However, this
can be changed by setting POINT_RELATIVE
,
INDEXED_FROM_ZERO
, or CLOCKWISE
in the indexFlags parameter.
ps
 stream used for printingindexFlags
 specifies index characteristics
(0 results in the default).getVertices()
,
getFaces()
public boolean check(PrintStream ps)
getDistanceTolerance
; see
check(PrintStream,double)
for details.ps
 print stream for diagnostic messages; may be
set to null
if no messages are desired.check(PrintStream,double)
public boolean check(PrintStream ps, double tol)
If the hull has been triangulated
,
then this routine may fail if some of the resulting
triangles are very small or thin.
ps
 print stream for diagnostic messages; may be
set to null
if no messages are desired.tol
 distance tolerancecheck(PrintStream)
Processing Library ComputationalGeometry by Mark Collins & Toru Hasegawa. (c) 2015