convexhull3d
Class ConvexHull3D

java.lang.Object
  |
  +--convexhull3d.ConvexHull3D

public class ConvexHull3D
extends java.lang.Object

Robustly computes the convex hull of a three dimensional set of points.

The computation is done using an insertion algorithm, with modifications to make it numercially robust. This includes making sure that all the faces deemed ``visible'' from a newly added point are connected (as described in Dey, Sugihara, and Bajaj, ``Delaunay triangulations in three dimensions with finite precision arithmetic'', Computer Aided Geometric Design 9 (1992) pp. 457--470). Marginally visible faces are also pruned, if necessary, to ensure that when the new point is added no faces with improper orientation will be generated.

By default, the hull is composed of a set of triangular faces, for which the associated vertices and faces may be obtained using the methods getHullFaceVertices and getHullFaces, respectively. However, merged faces can also be obtained using the methods getMergedFaceVertices and getMergedFaces. These are formed by merging adjacent faces whose vertices are coplanar to within numeric precision.

Author:
John E. Lloyd, Winter 2003

Field Summary
static double DBL_EPSILON
          Precision of a double.
 
Constructor Summary
ConvexHull3D(double[] coords)
          Constructs the convex hull of a set of 3D points given by coords.
 
Method Summary
 boolean containedInHull(SpatialPoint px)
          Returns true if a spatial point is on or inside the convex hull.
 boolean containedInHull(SpatialPoint px, double tol)
          Returns true if a spatial point is on or inside the convex hull.
 int[][] getHullFaces()
          Returns the triangular faces associated with this hull.
 SpatialPoint[] getHullFaceVertices()
          Returns an array of all the vertices used by the triangular faces of this hull.
 int[][] getMergedFaces()
          Returns the merged faces associated with this hull.
 SpatialPoint[] getMergedFaceVertices()
          Returns an array of all the vertices found in the merged faces of this hull.
 SpatialPoint[] getPoints()
          Returns an array of all the points from which this hull was constructed.
 void printHull(java.io.PrintStream ps, boolean notZeroIndexed)
          Prints the triangular faces (and associated vertices) of this hull to the stream ps.
 void printMergedHull(java.io.PrintStream ps, boolean notZeroIndexed)
          Prints the merged faces (and associated vertices) of this hull to the stream ps.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DBL_EPSILON

public static final double DBL_EPSILON
Precision of a double.

See Also:
Constant Field Values
Constructor Detail

ConvexHull3D

public ConvexHull3D(double[] coords)
             throws java.lang.IllegalArgumentException
Constructs the convex hull of a set of 3D points given by coords.

After construction, other methods can be used to obtain the hull's vertices and faces. If only three input points are specified, then the resulting ``hull'' will consist of two back-to-back triangles.

Parameters:
coords - an array containing the x,y,z coordinates of each point. The length of this array will be three times the number of points.
Throws:
java.lang.IllegalArgumentException - The number of input points is less than three.
Method Detail

getPoints

public SpatialPoint[] getPoints()
Returns an array of all the points from which this hull was constructed.

Returns:
points from which this hull was constructed

getHullFaceVertices

public SpatialPoint[] getHullFaceVertices()
Returns an array of all the vertices used by the triangular faces of this hull.

Returns:
array of vertices
See Also:
getHullFaces()

getHullFaces

public int[][] getHullFaces()
Returns the triangular faces associated with this hull.

Each face is represented as an integer array, which lists, in counter-clockwise order, the indices of its vertices (with respect to the array returned by getHullFaceVertices()).

Returns:
array of integer arrays, with each one listing the vertex indices for a particular face.
See Also:
getHullFaceVertices()

getMergedFaceVertices

public SpatialPoint[] getMergedFaceVertices()
Returns an array of all the vertices found in the merged faces of this hull.

Returns:
array of vertices
See Also:
getMergedFaces()

getMergedFaces

public int[][] getMergedFaces()
Returns the merged faces associated with this hull.

Merged faces are formed by merging adjacent triangular faces which are co-planar within numeric precision. Each face is represented as an integer array, which lists, in counter-clockwise order, the indices of its vertices (with respect to the array returned by getMergedFaceVertices()).

Returns:
array of integer arrays, with each one listing the vertex indices for a particular face.
See Also:
getMergedFaceVertices()

printHull

public void printHull(java.io.PrintStream ps,
                      boolean notZeroIndexed)
Prints the triangular faces (and associated vertices) of this hull to the stream ps.

The information is printed using the Alias Wavefront .obj file format, with the vertices printed first (each preceding by the letter v), followed by the face index sets (each preceded by the letter f).

Parameters:
ps - stream used for printing
notZeroIndexed - if false, then the index values for the face vertices are started at zero, rather than one. Indexing from one is standard for the .obj format.
See Also:
getHullFaces()

printMergedHull

public void printMergedHull(java.io.PrintStream ps,
                            boolean notZeroIndexed)
Prints the merged faces (and associated vertices) of this hull to the stream ps.

The information is printed using the Alias Wavefront .obj file format, with the vertices printed first (each preceding by the letter v), followed by the face index sets (each preceded by the letter f).

Parameters:
ps - stream used for printing
notZeroIndexed - if false, then the index values for the face vertices are started at zero, rather than one. Indexing from one is standard for the .obj format.
See Also:
getMergedFaces()

containedInHull

public boolean containedInHull(SpatialPoint px)
Returns true if a spatial point is on or inside the convex hull. This is the same as the method containedInHull (SpatialPoint, double), except that the numeric tolerance is computed automatically.

Parameters:
px - point to test
Returns:
true if the point is on or inside the hull
See Also:
containedInHull(SpatialPoint,double)

containedInHull

public boolean containedInHull(SpatialPoint px,
                               double tol)
Returns true if a spatial point is on or inside the convex hull. This is considered to be the case if the point is "inside" each of the hull's faces, or, more precisely, if its directed distance to each face (along the face's normal) is less than or equal to a user-supplied numeric tolerance. It is not unreasonable to set this tolerance to 0.

Parameters:
px - point to test
tol - numeric tolerance
Returns:
true if the point is on or inside the hull
See Also:
containedInHull(SpatialPoint)