\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.9 - 3D Convex Hulls
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Modules
3D Convex Hulls Reference

bunny.png
Susan Hert and Stefan Schirra
This package provides functions for computing convex hulls in three dimensions as well as functions for checking if sets of points are strongly convex or not. One can compute the convex hull of a set of points in three dimensions in two ways: using a static algorithm or using a triangulation to get a fully dynamic computation.


Introduced in: CGAL 1.1
Depends on: All algorithms produce as output a Polyhedron. The dynamic algorithms depend on 3D Triangulations.
BibTeX: cgal:hs-ch3-16b
License: GPL
Windows Demo: See Polyhedral Surface
Common Demo Dlls: dlls

A subset \(S \subseteq \mathbb{R}^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.

Classified Reference Pages

Concepts

Traits Classes

Convex Hull Functions

Convexity Checking Function

Halfspace Intersection Functions

Modules

 Concepts
 
 Traits Classes
 
 Convex Hull Functions
 The function convex_hull_3() computes the convex hull of a given set of three-dimensional points.
 
 Convexity Checking