CGAL 5.6.1  Convex Decomposition of Polyhedra

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...  
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 worstcase 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.
N
is bounded. Otherwise, the outer volume is ignored.N
is nonconvex, it is modified to represent the convex decomposition. If N
is convex, it is not modified.CGAL::Nef_polyhedron_3<Traits>