Peter Hachenberger

This packages provides a function for decomposing a bounded polyhedron into convex sub-polyhedra. The decomposition yields

$O(r^2)$ convex pieces, where

$r$ is the number of edges, whose adjacent facets form an angle of more than 180 degrees with respect to the polyhedron's interior. This bound is worst-case optimal.

Introduced in: CGAL 3.5
BibTeX: cgal:h-emspe-19b
License: GPL
Windows Demo: Polyhedron demo
Common Demo Dlls: dlls

Classified Reference Pages

Functions

CGAL::convex_decomposition_3(Nef_polyhedron_3& N)

Functions
template<typename Nef_polyhedron >
void	CGAL::convex_decomposition_3 (Nef_polyhedron &N)
	The function `convex_decomposition_3()` inserts additional facets into the given `Nef_polyhedron_3` `N`, such that each bounded marked volume (the outer volume is unbounded) is subdivided into convex pieces. More...

Function Documentation

◆ convex_decomposition_3()

template<typename Nef_polyhedron >

void CGAL::convex_decomposition_3 ( Nef_polyhedron & N )

#include <CGAL/convex_decomposition_3.h>

The function convex_decomposition_3() inserts additional facets into the given Nef_polyhedron_3 N, such that each bounded marked volume (the outer volume is unbounded) is subdivided into convex pieces.

The modified polyhedron represents a decomposition into $O(r^2)$ convex pieces, where $r$ is the number of edges that have two adjacent facets that span an angle of more than 180 degrees with respect to the interior of the polyhedron.

The worst-case running time of our implementation is $O(n^2r^4\sqrt[3]{nr^2}\log{(nr)})$ , where $n$ is the complexity of the polyhedron (the complexity of a Nef_polyhedron_3 is the sum of its Vertices, Halfedges and SHalfedges) and $r$ is the number of reflex edges.

Precondition: The polyhedron N is bounded. Otherwise, the outer volume is ignored.

Postcondition: If the polyhedron N is non-convex, it is modified to represent the convex decomposition. If N is convex, it is not modified.

See also: CGAL::Nef_polyhedron_3<Traits>

Examples:: Convex_decomposition_3/list_of_convex_parts.cpp.