CGAL 4.6.2 - 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) |
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(r2) 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(n2r43√nr2log(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 non-convex, it is modified to represent the convex decomposition. If N
is convex, it is not modified.CGAL::Nef_polyhedron_3<Traits>
#include <CGAL/convex_decomposition_3.h>