\( \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.13.1 - Convex Decomposition of Polyhedra
Functions
Convex Decomposition of Polyhedra Reference

Convex_decomposition_3-teaser.png
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-19a
License: GPL
Windows Demo: Polyhedron demo
Common Demo Dlls: dlls

Classified Reference Pages

Functions

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.