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(n²) 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.

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(n²) 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.