Class ConvexHull

java.lang.Object
com.treemap.swing.fastvoronoi.convexhull.Polytope
com.treemap.swing.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 Details

    • current

      protected int current
      Current vertex to add to the hull
    • created

      protected List<Facet> created
      List of newly created facets
    • horizon

      protected List<Edge> horizon
      List of edges on the horizon
    • visible

      protected List<Facet> 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))
      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.