Navigation: Up, Table of Contents, Bibliography, Index, Title Page

Chapter 4
3D Convex Hulls

Susan Hert and Stefan Schirra

A subset S 3 is convex if for any two points p and q in the set the line segment with endpoints p and q is contained in S. The convex hull of a set S is the smallest convex set containing S. The convex hull of a set of points P is a convex polytope with vertices in P. A point in P is an extreme point (with respect to P) if it is a vertex of the convex hull of P.

CGAL provides functions for computing convex hulls in two, three and arbitrary dimensions as well as functions for testing if a given set of points in is strongly convex or not. This chapter describes the functions available for three dimensions.

Assertions

The assertion flags for the convex hull and extreme point algorithms use CH in their names (e.g., CGAL_CH_NO_POSTCONDITIONS). For the convex hull algorithms, the postcondition check tests only convexity (if not disabled), but not containment of the input points in the polygon or polyhedron defined by the output points. The latter is considered an expensive checking and can be enabled by defining CGAL_CH_CHECK_EXPENSIVE .

Concepts

ConvexHullPolyhedron_3
ConvexHullPolyhedronFacet_3
ConvexHullPolyhedronHalfedge_3
ConvexHullPolyhedronVertex_3
ConvexHullTraits_3
IsStronglyConvexTraits_3

Traits Classes

CGAL::Convex_hull_traits_3<R>

Convex Hull Functions

CGAL::convex_hull_3
CGAL::convex_hull_incremental_3

Convexity Checking Function

CGAL::is_strongly_convex_3

Alphabetical Listing of Reference Pages

Next chapter: dD Convex Hulls and Delaunay Triangulations
Navigation: Table of Contents, Bibliography, Index, Title Page
The CGAL Project . Tue, December 21, 2004 .