Package com.macrofocus.treemap.fastvoronoi.convexhull

Class ConvexHull

java.lang.Object

com.macrofocus.treemap.fastvoronoi.convexhull.Polytope

com.macrofocus.treemap.fastvoronoi.convexhull.ConvexHull

public class ConvexHull
extends Polytope

ConvexHull is a 3D polytope which implements the randomized incremental algorithm for constructing a convex hull from a point cloud.

Field Summary

Fields

Modifier and Type	Field	Description
protected java.util.List<Facet>	created	List of newly created facets
protected int	current	Current vertex to add to the hull
protected java.util.List<Edge>	horizon	List of edges on the horizon
protected java.util.List<Facet>	visible	List of facets visible to the current vertex

Fields inherited from class com.macrofocus.treemap.fastvoronoi.convexhull.Polytope

points

Constructor Summary

Constructors

Constructor	Description
ConvexHull()

Method Summary

Modifier and Type	Method	Description
void	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	removeConflicts(Facet f)	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 hull
void	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.macrofocus.treemap.fastvoronoi.convexhull.Polytope

addFacet, addVertex, clear, getDiameter, getFacet, getFacetCount, getVertex, getVertexCount, removeFacet, removeVertex, setDiameter

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

current

protected int current

Current vertex to add to the hull

created

protected java.util.List<Facet> created

List of newly created facets

horizon

protected java.util.List<Edge> horizon

List of edges on the horizon

visible

protected java.util.List<Facet> visible

List of facets visible to the current vertex

Constructor Detail

ConvexHull

public ConvexHull()

Method Detail

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))

F(v) refers to the facets visible to vertex 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

public void addConflict(Facet f,
                        Vertex v)

Add an arc to the conflict graph connecting the given facet and vertex.

removeConflicts

public void removeConflicts(Facet f)

Remove all conflicts for the given facet.

addConflicts

public void addConflicts(Facet f,
                         Facet old1,
                         Facet old2)

Test all conflicts for the existing facet with the new facet. Add conflict arc for all vertices that can now see the new facet.