Next: Graphics Up: Basic Data Types for Previous: Rational Planes (d3_rat_plane)

3D Convex Hull Algorithms (d3_hull)

void CONVEX_HULL(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^2) in the worst case and O(nlog n) for most inputs.

bool CHECK_HULL(GRAPH<d3_rat_point,int> H)

a checker for convex hulls.

void CONVEX_HULL(list<d3_point> L, GRAPH<d3_point,int>& H)

a floating point version of CONVEX_HULL.

bool CHECK_HULL(GRAPH<d3_point,int> H)

a checker for floating-point convex hulls.

LEDA research project
1998-10-02

void	CONVEX_HULL(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^2) in the worst case and O(nlog n) for most inputs.
bool	CHECK_HULL(GRAPH<d3_rat_point,int> H)
		a checker for convex hulls.
void	CONVEX_HULL(list<d3_point> L, GRAPH<d3_point,int>& H)
		a floating point version of CONVEX_HULL.
bool	CHECK_HULL(GRAPH<d3_point,int> H)
		a checker for floating-point convex hulls.