next up previous contents index
Next: 3D Triangulation and Voronoi Up: Basic Data Types for Previous: Rational Simplices ( d3_rat_simplex   Contents   Index


3D Convex Hull Algorithms ( d3_hull )

void CONVEX_HULL(const list<d3_rat_point>& L, GRAPH<d3_rat_point,int>& H)
    CONVEX_HULL takes as argument a list of points and returns the (planar embedded) surface graph H of the convex hull of L. The algorithm is based on an incremental space sweep. The running time is O(n2) in the worst case and O(n log n) for most inputs.

bool CHECK_HULL(const GRAPH<d3_rat_point,int>& H)
    a checker for convex hulls.

void CONVEX_HULL(const list<d3_point>& L, GRAPH<d3_point,int>& H)
    a floating point version of CONVEX_HULL.

bool CHECK_HULL(const GRAPH<d3_point,int>& H)
    a checker for floating-point convex hulls.