Next: Graphics Up: Basic Data Types for Previous: Rational Simplices ( d3_rat_simplex Contents Index

3D Convex Hull Algorithms ( d3_hull )

1cm3cm

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

Next: Graphics Up: Basic Data Types for Previous: Rational Simplices ( d3_rat_simplex Contents Index

LEDA research project
2000-02-09

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