|
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.
|
|
| |
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.