Class ConvexHull
java.lang.Object
com.treemap.swing.fastvoronoi.convexhull.Polytope
com.treemap.swing.fastvoronoi.convexhull.ConvexHull
ConvexHull is a 3D polytope which implements the randomized
incremental algorithm for constructing a convex hull from a point
cloud.
-
Field Summary
FieldsModifier and TypeFieldDescriptionList of newly created facetsprotected int
Current vertex to add to the hullList of edges on the horizonList of facets visible to the current vertex -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
addConflict
(Facet f, Vertex v) Add an arc to the conflict graph connecting the given facet and vertex.void
addConflicts
(Facet f, Facet old1, Facet old2) Test all conflicts for the existing facet with the new facet.void
compute()
Computation method for the convex hull, after the algorithm in the Book of Mark de Berg and the others.void
Remove all conflicts for the given facet.void
restart()
Clear existing vertices and facets and generate a new random point cloud.void
step()
Add the next vertex to the convex hullvoid
stepA()
StepA begins an incremental step of the algorithm.void
stepB()
StepB continues the incremental step by conneting vertex v to each edge of the horizon.void
stepC()
StepC cleans up the process started in steps A and B by removing all of the previously visible facets (including the corresponding nodes and edges in the conflict graph).Methods inherited from class com.treemap.swing.fastvoronoi.convexhull.Polytope
addFacet, addVertex, clear, getDiameter, getFacet, getFacetCount, getVertex, getVertexCount, removeFacet, removeVertex, setDiameter
-
Field Details
-
current
protected int currentCurrent vertex to add to the hull -
created
List of newly created facets -
horizon
List of edges on the horizon -
visible
List of facets visible to the current vertex
-
-
Constructor Details
-
ConvexHull
public ConvexHull()
-
-
Method Details
-
compute
public void compute()Computation method for the convex hull, after the algorithm in the Book of Mark de Berg and the others. -
restart
public void restart()Clear existing vertices and facets and generate a new random point cloud. -
step
public void step()Add the next vertex to the convex hull -
stepA
public void stepA()StepA begins an incremental step of the algorithm.- Identify the next vertex v. O(1)
- Identify all facets visible to v. O(F(v))
- Find the list of horizon edges for v. O(F(v))
-
stepB
public void stepB()StepB continues the incremental step by conneting vertex v to each edge of the horizon. -
stepC
public void stepC()StepC cleans up the process started in steps A and B by removing all of the previously visible facets (including the corresponding nodes and edges in the conflict graph). -
addConflict
Add an arc to the conflict graph connecting the given facet and vertex. -
removeConflicts
Remove all conflicts for the given facet. -
addConflicts
Test all conflicts for the existing facet with the new facet. Add conflict arc for all vertices that can now see the new facet.
-