|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--convexhull3d.ConvexHull3D
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.
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 |
public static final double DBL_EPSILON
Constructor Detail |
public ConvexHull3D(double[] coords) throws java.lang.IllegalArgumentException
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.
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.
java.lang.IllegalArgumentException
- The number of input points
is less than three.Method Detail |
public SpatialPoint[] getPoints()
public SpatialPoint[] getHullFaceVertices()
getHullFaces()
public int[][] getHullFaces()
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()).
getHullFaceVertices()
public SpatialPoint[] getMergedFaceVertices()
getMergedFaces()
public int[][] getMergedFaces()
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()).
getMergedFaceVertices()
public void printHull(java.io.PrintStream ps, boolean notZeroIndexed)
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
).
ps
- stream used for printingnotZeroIndexed
- 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.getHullFaces()
public void printMergedHull(java.io.PrintStream ps, boolean notZeroIndexed)
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
).
ps
- stream used for printingnotZeroIndexed
- 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.getMergedFaces()
public boolean containedInHull(SpatialPoint px)
containedInHull (SpatialPoint, double)
,
except that the numeric tolerance is computed automatically.
px
- point to test
containedInHull(SpatialPoint,double)
public boolean containedInHull(SpatialPoint px, double tol)
px
- point to testtol
- numeric tolerance
containedInHull(SpatialPoint)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |