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

◆ Mark

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.

◆ Object_handle

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

◆ Boundary

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

◆ Content

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

◆ Intersection_mode

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

◆ Nef_polyhedron_3() [1/4]

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

PolygonMesh	a model of `FaceListGraph` and `VertexListGraph`.
HalfedgeIndexMap	a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::halfedge_descriptor` as key type a value type convertible to `std::size_t`
FaceIndexMap	a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type a value type convertible to `std::size_t`

◆ Nef_polyhedron_3() [2/4]

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.

◆ Nef_polyhedron_3() [3/4]

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.

◆ Nef_polyhedron_3() [4/4]

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

◆ convert_to_polyhedron()

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.

◆ intersection()

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.

◆ join()

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

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 >

Classes

Types

Creation

Access Member Functions

Point Set Predicates

Unary Set Operations

Binary Set Operations

Operations

Member Typedef Documentation

◆ Mark

◆ Object_handle

Member Enumeration Documentation

◆ Boundary

◆ Content

◆ Intersection_mode

Constructor & Destructor Documentation

◆ Nef_polyhedron_3() [1/4]

◆ Nef_polyhedron_3() [2/4]

◆ Nef_polyhedron_3() [3/4]

◆ Nef_polyhedron_3() [4/4]

Member Function Documentation

◆ convert_to_polyhedron()

◆ intersection()

◆ join()

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 >