\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.10 - 3D Boolean Operations on Nef Polyhedra
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 > Class Template Reference

#include <CGAL/Nef_polyhedron_3.h>

Definition

template<class Nef_polyhedronTraits_3, class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
class CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >

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.

See Also
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>
Examples:
Nef_3/comparison.cpp, Nef_3/complex_construction.cpp, Nef_3/exploration_SM.cpp, Nef_3/extended_kernel.cpp, Nef_3/handling_double_coordinates.cpp, Nef_3/interface_polyhedron.cpp, Nef_3/nef_3_construction.cpp, Nef_3/nef_3_point_location.cpp, Nef_3/nef_3_simple.cpp, Nef_3/nef_3_to_surface_mesh.cpp, Nef_3/nefIO.cpp, Nef_3/offIO.cpp, Nef_3/point_set_operations.cpp, Nef_3/polyline_construction.cpp, Nef_3/set_operations.cpp, Nef_3/shell_exploration.cpp, Nef_3/topological_operations.cpp, and Nef_3/transformation.cpp.

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.
 
template<class PolygonMesh , class HalfedgeIndexMap , class FaceIndexMap >
 Nef_polyhedron_3 (const PolygonMesh &pm, const HalfedgeIndexMap &him, const FaceIndexMap &fim)
 creates a Nef polyhedron, which represents the same point set as the polyhedral surface pm does. More...
 
 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: CGAL_forall_vertices(v,N), CGAL_forall_halfedges(e,N), CGAL_forall_edges(e,N), CGAL_forall_halffacets(f,N), CGAL_forall_facets(f,N), CGAL_forall_volumes(c,N) where N is a Nef_polyhedron_3.

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< Traitscomplement () const
 returns the complement of N .
 
Nef_polyhedron_3< Traitsinterior () const
 returns the interior of N .
 
Nef_polyhedron_3< Traitsboundary () const
 returns the boundary of N .
 
Nef_polyhedron_3< Traitsclosure () const
 returns the closure of N .
 
Nef_polyhedron_3< Traitsregularization () const
 returns the regularization, i.e. the closure of the interior, of N .
 
Nef_polyhedron_3< Traitsoperator! () const
 returns the complement of N .
 

Binary Set Operations

Nef_polyhedron_3< Traitsintersection (const Nef_polyhedron_3< Traits > &N1) const
 return the intersection of N and N1.
 
Nef_polyhedron_3< Traitsjoin (const Nef_polyhedron_3< Traits > &N1) const
 return the union of N and N1. More...
 
Nef_polyhedron_3< Traitsdifference (const Nef_polyhedron_3< Traits > &N1) const
 return the difference between N and N1.
 
Nef_polyhedron_3< Traitssymmetric_difference (const Nef_polyhedron_3< Traits > &N1) const
 return the symmetric difference of N and N1.
 
Nef_polyhedron_3< Traitsintersection (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< Traitsoperator* (const Nef_polyhedron_3< Traits > &N1) const
 return the intersection of N and N1.
 
Nef_polyhedron_3< Traitsoperator+ (const Nef_polyhedron_3< Traits > &N1) const
 return the union of N and N1.
 
Nef_polyhedron_3< Traitsoperator- (const Nef_polyhedron_3< Traits > &N1) const
 return the difference between N and N1.
 
Nef_polyhedron_3< Traitsoperator^ (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 triangulated 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.
 

Member Typedef Documentation

template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
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.

template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = 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.

Member Enumeration Documentation

template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
enum CGAL::Nef_polyhedron_3::Boundary

construction selection.

Enumerator
EXCLUDED 
INCLUDED 
template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
enum CGAL::Nef_polyhedron_3::Content

construction selection.

Enumerator
EMPTY 
COMPLETE 
template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
enum CGAL::Nef_polyhedron_3::Intersection_mode

intersection selection.

Enumerator
CLOSED_HALFSPACE 
OPEN_HALFSPACE 
PLANE_ONLY 

Constructor & Destructor Documentation

template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
template<class PolygonMesh , class HalfedgeIndexMap , class FaceIndexMap >
CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::Nef_polyhedron_3 ( const PolygonMesh &  pm,
const HalfedgeIndexMap &  him,
const FaceIndexMap &  fim 
)
explicit

creates a Nef polyhedron, which represents the same point set as the polyhedral surface pm does.

him and fim must be both initialized so that halfedges and faces are indexed in [0, num_halfedges(pm)[ and [0, num_faces(pm)[ respectively. If PolygonMesh has an internal halfedge index map and an internal face index map, the last two parameters can be omitted.

Template Parameters
PolygonMesha model of FaceListGraph and VertexListGraph.
HalfedgeIndexMapa class model of ReadablePropertyMap with boost::graph_traits<PolygonMesh>::halfedge_descriptor as key type a value type convertible to std::size_t
FaceIndexMapa class model of ReadablePropertyMap with boost::graph_traits<PolygonMesh>::face_descriptor as key type a value type convertible to std::size_t
template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
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.

template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
template<class Forward_iterator >
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.

template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
template<class Forward_iterator >
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.

Member Function Documentation

template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
void CGAL::Nef_polyhedron_3< Nef_polyhedronTraits_3, Nef_polyhedronItems_3 >::convert_to_polyhedron ( Polyhedron P) const

converts N into a triangulated Polyhedron.

For conversion to other types, see convert_nef_polyhedron_to_polygon_mesh().

Precondition
N is simple.
template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
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.

template<class Nef_polyhedronTraits_3 , class Nef_polyhedronItems_3 = CGAL::Default_items<Nef_polyhedronTraits_3> class Nef_polyhedronMarks = bool>
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.)