Reference Manual

Todo:

fix or keep the Default_traits

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, checking if two convex hulls intersect and computing the distance between them if they do not. One can compute the convex hull of a set of points in three dimensions in three ways: using a static algorithm, using a triangulation to get a fully dynamic computation or using the specific data structure Convex_hull_hierarchy for optimal intersection testing.

Introduced in: CGAL 1.1
Depends on: The dynamic algorithms depend on 3D Triangulations.
BibTeX: cgal:hs-ch3-26a
License: GPL
Windows Demo: CGAL Lab

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, checking if two convex hulls intersect and computing the distance between them if they do not. This chapter describes the functions available for three dimensions.

Assertions

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_CHECK_EXPENSIVE.

Classified Reference Pages

Concepts

• ConvexHullTraits_3
• IsStronglyConvexTraits_3

Traits Classes

• CGAL::Convex_hull_traits_3<R>
• CGAL::Extreme_points_traits_adapter_3

Intersection Test

• CGAL::Convex_hull_3::do_intersect()

Convex Hull Functions

• CGAL::convex_hull_3()
• CGAL::extreme_points_3()
• CGAL::make_extreme_points_traits_adapter()

Directional Queries

• CGAL::extreme_point_3()
• CGAL::extreme_vertex_3()

Acceleration Structures

• CGAL::Convex_hull_hierarchy

Convexity Checking Function

• CGAL::is_strongly_convex_3

Halfspace Intersection Functions

• CGAL::halfspace_intersection_3()
• CGAL::halfspace_intersection_with_constructions_3()
• CGAL::halfspace_intersection_interior_point_3()

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

Classes
struct	CGAL::Convex_hull_hierarchy< PolygonMesh >
	This class stores a convex hull in a data structure optimized for fast intersection tests. More...