Function

CGAL::convex_decomposition_3

Definition

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 unbouned) 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(n2r4root3(nr2)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.

void convex_decomposition_3 ( Nef_polyhedron_3& N)

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>