|
CGAL 4.9 - 3D Boolean Operations on Nef Polyhedra
|
|
CGAL 4.9 - 3D Boolean Operations on Nef Polyhedra
|
#include <CGAL/Nef_polyhedron_3.h>
A 3D Nef polyhedron is a subset of the 3-dimensional space that is the result of forming complements and intersections starting from a finite set H of 3-dimensional halfspaces.
Nef polyhedra are closed under all binary set operations, i.e., intersection, union, difference, complement, and under the topological operations boundary, closure, and interior.
A 3D Nef polyhedron can be represented by the local pyramids of the minimal elements of its incidence structure. Without going into to much detail, a local pyramid essentially reflects the topologic and geometric situation at a certain location in a point set. For finite polyhedra the minimal elements of the incidence structure are vertices only. This means, that it suffices to model the topological and geometric situation of the vertices. For 3D Nef polyhedra, the local pyramid of a vertex is represented by a planar Nef polyhedra embedded on a sphere.
A Nef_polyhedron_3 consists of vertices V, a sphere map for each vertex in V, edges E, facets F, volumes C, a mark for every item, and an incidence relation on them. Each edge and each facet is represented by two halfedges or two halffacets, respectively.
Template Parameters
The first parameter requires one of the following exact kernels: Homogeneous, Simple_homogeneous, Extended_homogeneous parametrized with Gmpz, leda_integer or any other number type modeling \(\mathbb{Z}\), or Cartesian, Simple_cartesian, Extended_cartesian parametrized with Gmpq, leda_rational, Quotient<Gmpz> or any other number type modeling \(\mathbb{Q}\).
The second parameter and the third parameter are for future considerations. Neither Nef_polyhedronItems_3 nor Nef_polyhedronMarks is specifed, yet. Do not use any other than the default types for these two template parameters.
CGAL::Nef_polyhedron_3::Vertex CGAL::Nef_polyhedron_3::Halfedge CGAL::Nef_polyhedron_3::Halffacet CGAL::Nef_polyhedron_3::Volume CGAL::Nef_polyhedron_3::SHalfedge CGAL::Nef_polyhedron_3::SHalfloop CGAL::Nef_polyhedron_3::SFace CGAL::Nef_polyhedron_S2<Traits> CGAL::Polyhedron_3<Traits> Classes | |
| class | Halfedge |
| A Halfedge has a double meaning. More... | |
| class | Halffacet |
| A halffacet is an oriented, rectilinear bounded part of a plane. More... | |
| class | Halffacet_cycle_iterator |
The type Halffacet_cycle_iterator iterates over a list of Object_handles. More... | |
| class | SFace |
| An sface is described by its boundaries. More... | |
| class | SFace_cycle_iterator |
The type SFace_cycle_iterator iterates over a list of Object_handles. More... | |
| class | SHalfedge |
| A shalfedge is a great arc on a sphere map. More... | |
| class | SHalfloop |
| A shalfloop is a great circle on a sphere map. More... | |
| class | Vertex |
| A vertex is a point in the 3-dimensional space. More... | |
| class | Volume |
| A volume is a full-dimensional connected point set in \( \mathbb{R}^3\). More... | |
Types | |
| enum | Boundary { EXCLUDED, INCLUDED } |
| construction selection. More... | |
| enum | Content { EMPTY, COMPLETE } |
| construction selection. More... | |
| enum | Intersection_mode { CLOSED_HALFSPACE, OPEN_HALFSPACE, PLANE_ONLY } |
| intersection selection. More... | |
| typedef unspecified_type | Mark |
| All object (vertices, edges, etc.) are attributed by a Mark. More... | |
| typedef unspecified_type | size_type |
size type of Nef_polyhedron_3. | |
| typedef unspecified_type | Vertex_const_handle |
| non-mutable handle to a vertex. | |
| typedef unspecified_type | Halfedge_const_handle |
| non-mutable handle to a halfedge. | |
| typedef unspecified_type | Halffacet_const_handle |
| non-mutable handle to a halffacet. | |
| typedef unspecified_type | Volume_const_handle |
| non-mutable handle to a volume. | |
| typedef unspecified_type | SVertex_const_handle |
| non-mutable handle to a svertex. | |
| typedef unspecified_type | SHalfedge_const_handle |
| non-mutable handle to a shalfedge. | |
| typedef unspecified_type | SHalfloop_const_handle |
| non-mutable handle to a shalfloop. | |
| typedef unspecified_type | SFace_const_handle |
| non-mutable handle to a sface. | |
| typedef unspecified_type | Vertex_const_iterator |
| non-mutable iterator over all vertices. | |
| typedef unspecified_type | Halfedge_const_iterator |
| non-mutable iterator over all halfeges. | |
| typedef unspecified_type | Halffacet_const_iterator |
| non-mutable iterator over all halffacets. | |
| typedef unspecified_type | Volume_const_iterator |
| non-mutable iterator over all volumes. | |
| typedef unspecified_type | SVertex_const_iterator |
| non-mutable iterator over all svertices. | |
| typedef unspecified_type | SHalfedge_const_iterator |
| non-mutable iterator over all shalfedges. | |
| typedef unspecified_type | SHalfloop_const_iterator |
| non-mutable iterator over all shalfloops. | |
| typedef unspecified_type | SFace_const_iterator |
| non-mutable iterator over all sfaces. | |
| typedef unspecified_type | SHalfedge_around_svertex_const_circulator |
| non-mutable circulator of shalfedges around a svertex (cw). | |
| typedef unspecified_type | SHalfedge_around_sface_const_circulator |
| non-mutable circulator of shalfedges around a sface (ccw). | |
| typedef unspecified_type | SHalfedge_around_facet_const_circulator |
| non-mutable circulator of shalfedges around a halffacet (ccw). | |
| typedef unspecified_type | SFace_cycle_const_iterator |
| non-mutable iterator over the cylces of a sface. | |
| typedef unspecified_type | Halffacet_cycle_const_iterator |
| non-mutable iterator over the cylces of a halffacet. | |
| typedef unspecified_type | Shell_entry_const_iterator |
| non-mutable iterator providing an entry to each shell. | |
| typedef unspecified_type | Object_handle |
| a generic handle to an object. More... | |
| typedef unspecified_type | Point_3 |
| location of vertices. | |
| typedef unspecified_type | Segment_3 |
| segment represented by a halfedge. | |
| typedef unspecified_type | Vector_3 |
| direction of a halfedge. | |
| typedef unspecified_type | Plane_3 |
| plane of a halffacet lies in. | |
| typedef unspecified_type | Aff_transformation_3 |
| affine transformation. | |
| typedef unspecified_type | Polylines_tag |
| tag for calling polyline constructor. | |
| typedef unspecified_type | Points_tag |
| tag for calling point constructor. | |
| typedef unspecified_type | Nef_polyhedron_S2 |
| a sphere map. | |
| typedef unspecified_type | Polyhedron |
| a polyhedral surface. | |
Creation | |
| Nef_polyhedron_3 (Content space=EMPTY) | |
creates a Nef polyhedron and initializes it to the empty set if plane == EMPTY and to the whole space if space == COMPLETE. | |
| Nef_polyhedron_3 (const Plane_3 &p, Boundary b=INCLUDED) | |
creates a Nef polyhedron containing the halfspace on the negative side of p including p if b==INCLUDED, excluding p if b==EXCLUDED. | |
| Nef_polyhedron_3 (Polyhedron &P) | |
creates a Nef polyhedron, which represents the same point set as the polyhedral surface P does. | |
| Nef_polyhedron_3 (Input_iterator begin, Input_iterator end) | |
creates a Nef polyhedron consisting of a single polygon spanned by the list of points in the iterator range [begin,end). More... | |
| template<class Forward_iterator > | |
| Nef_polyhedron_3 (Forward_iterator it, Forward_iterator end, Polylines_tag) | |
| creates a Nef polyhedron consisting of polylines. More... | |
| template<class Forward_iterator > | |
| Nef_polyhedron_3 (Forward_iterator it, Forward_iterator end, Points_tag) | |
| creates a Nef polyhedron that consists only of points. More... | |
| Nef_polyhedron_3 (const Point_3 &p) | |
| creates a Nef polyhedron that consists of point p. | |
| Nef_polyhedron_3 (const Segment_3 &s) | |
| creates a Nef polyhedron that consists of segment s. | |
Access Member Functions | |
The following macros are provided: | |
| bool | is_simple () const |
returns true, if N is a 2-manifold. | |
| bool | is_valid () const |
checks the integrity of N . | |
| Size_type | number_of_vertices () const |
| returns the number of vertices. | |
| Size_type | number_of_halfedges () const |
| return the number of halfedges. | |
| Size_type | number_of_edges () const |
| returns the number of halfedge pairs. | |
| Size_type | number_of_halffacets () const |
| returns the number of halffacets. | |
| Size_type | number_of_facets () const |
| returns the number of halffacet pairs. | |
| Size_type | number_of_volumes () const |
| returns the number of volumes. | |
| Vertex_const_iterator | vertices_begin () const |
| iterator over all vertices. | |
| Vertex_const_iterator | vertices_end () const |
| past-the-end iterator. | |
| Halfedge_const_iterator | halfedges_begin () const |
| iterator over all halfedges. | |
| Halfedge_const_iterator | halfedges_end () const |
| past-the-end iterator. | |
| Halffacet_const_iterator | halffacets_begin () const |
| iterator over all halffacets. | |
| Halffacet_const_iterator | halffacets_end () const |
| past-the-end iterator. | |
| Volume_const_iterator | volumes_begin () const |
| iterator over all volumes. | |
| Volume_const_iterator | volumes_end () const |
| past-the-end iterator. | |
| Object_handle | locate (const Point_3 &p) const |
| returns a generic handle to the object (vertex, edge, facet or volume) which contains the point p in its relative interior. | |
| Nef_polyhedron_S2 | get_sphere_map (Vertex_const_iterator v) const |
returns the neighborhood of a vertex modeled by a Nef_polyhedron_S2. | |
Point Set Predicates | |
| bool | is_empty () const |
returns true, if N is the empty point set. | |
| bool | is_space () const |
returns true, if N is the complete 3D space. | |
| bool | operator== (const Nef_polyhedron_3< Traits > &N1) const |
returns true, if N and N1 comprise the same point sets. | |
| bool | operator!= (const Nef_polyhedron_3< Traits > &N1) const |
returns true, if N and N1 comprise different point sets. | |
| bool | operator< (const Nef_polyhedron_3< Traits > &N1) const |
returns true, if N is a proper subset of N1. | |
| bool | operator> (const Nef_polyhedron_3< Traits > &N1) const |
returns true, if N is a proper superset of N1. | |
| bool | operator<= (const Nef_polyhedron_3< Traits > &N1) const |
returns true, if N is a subset of N1. | |
| bool | operator>= (const Nef_polyhedron_3< Traits > &N1) const |
returns true, if N is a superset of N1. | |
Unary Set Operations | |
| Nef_polyhedron_3< Traits > | complement () const |
returns the complement of N . | |
| Nef_polyhedron_3< Traits > | interior () const |
returns the interior of N . | |
| Nef_polyhedron_3< Traits > | boundary () const |
returns the boundary of N . | |
| Nef_polyhedron_3< Traits > | closure () const |
returns the closure of N . | |
| Nef_polyhedron_3< Traits > | regularization () const |
returns the regularization, i.e. the closure of the interior, of N . | |
| Nef_polyhedron_3< Traits > | operator! () const |
returns the complement of N . | |
Binary Set Operations | |
| Nef_polyhedron_3< Traits > | intersection (const Nef_polyhedron_3< Traits > &N1) const |
return the intersection of N and N1. | |
| Nef_polyhedron_3< Traits > | join (const Nef_polyhedron_3< Traits > &N1) const |
return the union of N and N1. More... | |
| Nef_polyhedron_3< Traits > | difference (const Nef_polyhedron_3< Traits > &N1) const |
return the difference between N and N1. | |
| Nef_polyhedron_3< Traits > | symmetric_difference (const Nef_polyhedron_3< Traits > &N1) const |
return the symmetric difference of N and N1. | |
| Nef_polyhedron_3< Traits > | intersection (const Plane_3 &p, Intersection_mode im) const |
returns intersection of N with plane (im=PLANE_ONLY), open halfspace (im=OPEN_HALFSPACE), or closed halfspace (im=CLOSED_HALFSPACE). More... | |
| Nef_polyhedron_3< Traits > | operator* (const Nef_polyhedron_3< Traits > &N1) const |
return the intersection of N and N1. | |
| Nef_polyhedron_3< Traits > | operator+ (const Nef_polyhedron_3< Traits > &N1) const |
return the union of N and N1. | |
| Nef_polyhedron_3< Traits > | operator- (const Nef_polyhedron_3< Traits > &N1) const |
return the difference between N and N1. | |
| Nef_polyhedron_3< Traits > | operator^ (const Nef_polyhedron_3< Traits > &N1) const |
return the symmetric difference of N and N1. | |
| void | operator*= (const Nef_polyhedron_3< Traits > &N1) |
intersects N and N1. | |
| void | operator+= (const Nef_polyhedron_3< Traits > &N1) |
unites N with N1. | |
| void | operator-= (const Nef_polyhedron_3< Traits > &N1) |
subtracts N1 from N . | |
| void | operator^= (const Nef_polyhedron_3< Traits > &N1) |
performs a symmetric intersection of N and N1. | |
Operations | |
| void | clear (Content space=EMPTY) |
make N the empty set if space == EMPTY and the complete 3D space if space == COMPLETE. | |
| void | transform (const Aff_transformation_3 &aff) |
applies an affine transformation to N . | |
| void | convert_to_polyhedron (Polyhedron &P) const |
converts N into a Polyhedron. More... | |
| void | visit_shell_objects (SFace_const_handle f, Visitor &V) const |
calls the visit function of V for every item which belongs to the same shell as sf. | |
| typedef unspecified_type CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::Mark |
All object (vertices, edges, etc.) are attributed by a Mark.
Mark equals bool.
| typedef unspecified_type CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::Object_handle |
a generic handle to an object.
The kind of object (vertex, halfedge, halffacet, volume, svertex, shalfedge, shalfloop, sface) can be determined and the object can be assigned to a corresponding constant handle by one of the following functions:
bool assign(Vertex_const_handle& h, Object_handle)
bool assign(Halfedge_const_handle& h, Object_handle)
bool assign(Halffacet_const_handle& h, Object_handle)
bool assign(Volume_const_handle& h, Object_handle)
bool assign(SVertex_const_handle& h, Object_handle)
bool assign(SHalfedge_const_handle& h, Object_handle)
bool assign(SHalfloop_const_handle& h, Object_handle)
bool assign(SFace_const_handle& h, Object_handle)
where each function returns true iff the assignment to h could be accomplished.
| enum CGAL::Nef_polyhedron_3::Boundary |
| enum CGAL::Nef_polyhedron_3::Content |
| enum CGAL::Nef_polyhedron_3::Intersection_mode |
| CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::Nef_polyhedron_3 | ( | Input_iterator | begin, |
| Input_iterator | end | ||
| ) |
creates a Nef polyhedron consisting of a single polygon spanned by the list of points in the iterator range [begin,end).
If the points do not lie on a common supporting plane, the constructor tries to triangulate the polygon into multiple facets.If the construction does not succeed, the empty set is created.
| CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::Nef_polyhedron_3 | ( | Forward_iterator | it, |
| Forward_iterator | end, | ||
| Polylines_tag | |||
| ) |
creates a Nef polyhedron consisting of polylines.
The iterator range [it, end) defines a range of polylines. Each polyline is defined as a range of points, first and past-the-end iterators being provided as a std::pair of iterators.
| CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::Nef_polyhedron_3 | ( | Forward_iterator | it, |
| Forward_iterator | end, | ||
| Points_tag | |||
| ) |
creates a Nef polyhedron that consists only of points.
The iterator range [it, end) defines a range of points.
| void CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::convert_to_polyhedron | ( | Polyhedron & | P) | const |
converts N into a Polyhedron.
N is simple. | Nef_polyhedron_3<Traits> CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::intersection | ( | const Plane_3 & | p, |
| Intersection_mode | im | ||
| ) | const |
returns intersection of N with plane (im=PLANE_ONLY), open halfspace (im=OPEN_HALFSPACE), or closed halfspace (im=CLOSED_HALFSPACE).
In the latter two cases, the halfspaces are on the negative side of the plane p. The function is written for the use with standard kernels, where halfspaces are not part of the domain. The function does not work in combination with an extended kernels or with an unbounded polyhedron.
| Nef_polyhedron_3<Traits> CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::join | ( | const Nef_polyhedron_3< Traits > & | N1) | const |
return the union of N and N1.
(Note that ''union'' is a C++ keyword and cannot be used for this operation.)
1.8.4