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.


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