#include <CGAL/Nef_polyhedron_S2.h>

Definition

template<typename Traits>
class CGAL::Nef_polyhedron_S2< Traits >

An instance of data type Nef_polyhedron_S2<Traits> is a subset of the sphere \( S_2\) that is the result of forming complements and intersections starting from a finite set H of halfspaces bounded by a plane containing the origin. Halfspaces correspond to hemispheres of \( S_2\) and are therefore modeled by oriented great circles of type Sphere_circle. Nef_polyhedron_S2 is closed under all binary set operations intersection, union, difference, complement and under the topological operations boundary, closure, and interior.

Parameters

template< class Nef_polyhedronTraits_S2,
          class Nef_polyhedronItems_S2 = CGAL::SM_items,
          class Nef_polyhedronMarks = bool >
class Nef_polyhedron_S2;

The first parameter requires one of the following exact kernels: Homogeneous, Simple_homogeneous parametrized with Gmpz, leda_integer or any other number type modeling \(\mathbb{Z}\), or Cartesian, Simple_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_S2 nor Nef_polyhedronMarks is specifed, yet. Do not use other than the default types for these two template parameters.

Exploration - Point location - Ray shooting

As Nef polyhedra are the result of forming complements and intersections starting from a set H of half-spaces that are defined by oriented lines in the plane, they can be represented by an attributed plane map \( M = (V,E,F)\). For topological queries within M the following types and operations allow exploration access to this structure.

Input and Output

A Nef polyhedron N can be visualized in an open GL window. The output operator is defined in the file CGAL/IO/Nef_polyhedron_2_Window-stream.h.

Implementation

Nef polyhedra are implemented on top of a halfedge data structure and use linear space in the number of vertices, edges and facets. Operations like empty take constant time. The operations clear, complement, interior, closure, boundary, regularization, input and output take linear time. All binary set operations and comparison operations take time \( O(n \log n)\) where \( n\) is the size of the output plus the size of the input.

The point location and ray shooting operations are implemented in the naive way. The operations run in linear query time without any preprocessing.

Examples: Nef_S2/nef_s2_construction.cpp, Nef_S2/nef_s2_exploration.cpp, Nef_S2/nef_s2_point_location.cpp, and Nef_S2/nef_s2_simple.cpp.

Classes
class	SFace

class	SFace_cycle_iterator

class	SHalfedge

class	SHalfloop

class	Sphere_circle

class	Sphere_point

class	Sphere_segment

class	SVertex

Types
enum	Boundary { EXCLUDED, INCLUDED }
	construction selection. More...

enum	Content { EMPTY, COMPLETE }
	construction selection. More...

typedef unspecified_type	SVertex_const_handle
	non-mutable handle to svertex. More...

typedef unspecified_type	SHalfedge_const_handle
	non-mutable handle to shalfedge. More...

typedef unspecified_type	SHalfloop_const_handle
	non-mutable handle to shalfloop. More...

typedef unspecified_type	SFace_const_handle
	non-mutable handle to sface. More...

typedef unspecified_type	SVertex_const_iterator
	non-mutable iterator over all svertices. More...

typedef unspecified_type	SHalfedge_const_iterator
	non-mutable iterator over all shalfedges. More...

typedef unspecified_type	SHalfloop_const_iterator
	non-mutable iterator over all shalfloops. More...

typedef unspecified_type	SFace_const_iterator
	non-mutable iterator over all sfaces. More...

typedef unspecified_type	SHalfedge_around_svertex_const_circulator
	circulating the adjacency list of an svertex `v`. More...

typedef unspecified_type	SHalfedge_around_sface_const_circulator
	circulating the sface cycle of an sface `f`. More...

typedef unspecified_type	SFace_cycle_const_iterator
	iterating all sface cycles of an sface `f`. More...

typedef unspecified_type	Mark
	attributes of objects (vertices, edges, faces). More...

typedef unspecified_type	size_type
	size type More...

typedef unspecified_type	Object_handle
	a generic handle to an object of the underlying plane map. More...

Creation
	Nef_polyhedron_S2 (Content sphere=EMPTY)
	creates an instance `N` of type `Nef_polyhedron_S2<K>` and initializes it to the empty set if `sphere == EMPTY` and to the whole sphere if `sphere == COMPLETE`. More...

	Nef_polyhedron_S2 (Sphere_circle c, Boundary circle=INCLUDED)
	creates a Nef polyhedron `N` containing the half-sphere left of `c` including `c` if `circle==INCLUDED`, excluding `c` if `circle==EXCLUDED`. More...

template<class Forward_iterator >
	Nef_polyhedron_S2 (Forward_iterator first, Forward_iterator beyond, Boundary b=INCLUDED)
	creates a Nef polyhedron `N` from the set of sphere segments in the iterator range `[first,beyond)`. More...

Operations
void	clear (Content plane=EMPTY)
	makes `N` the empty set if `plane == EMPTY` and the full plane if `plane == COMPLETE`. More...

bool	is_empty ()
	returns true if `N` is empty, false otherwise. More...

bool	is_sphere ()
	returns true if `N` is the whole sphere, false otherwise. More...

bool	contains (Object_handle h)
	returns true iff the object `h` is contained in the set represented by `N`. More...

bool	contained_in_boundary (Object_handle h)
	returns true iff the object `h` is contained in the \( 1\)-skeleton of `N`. More...

Object_handle	locate (const Sphere_point &p)
	returns a generic handle `h` to an object (face, halfedge, vertex) of the underlying plane map that contains the point `p` in its relative interior. More...

Object_handle	ray_shoot (const Sphere_point &p, const Sphere_direction &d)
	returns a handle `h` with `N.contains(h)` that can be converted to a `Vertex_/Halfedge_/Face_const_handle` as described above. More...

Object_handle	ray_shoot_to_boundary (const Sphere_point &p, const Sphere_direction &d)
	returns a handle `h` that can be converted to a `Vertex_/Halfedge_const_handle` as described above. More...

Constructive Operations
Additionally there are operators `,+,-,^,!` which implement the binary operations intersection, union, difference, symmetric difference, and the unary operation complement* respectively. There are also the corresponding modification operations `<,<=,>,>=,==,!=`. There are also comparison operations like `<,<=,>,>=,==,!=` which implement the relations subset, subset or equal, superset, superset or equal, equality, inequality, respectively.
Nef_polyhedron_S2< K >	complement ()
	returns the complement of `N` in the plane. More...

Nef_polyhedron_S2< K >	interior ()
	returns the interior of `N`. More...

Nef_polyhedron_S2< K >	closure ()
	returns the closure of `N`. More...

Nef_polyhedron_S2< K >	boundary ()
	returns the boundary of `N`. More...

Nef_polyhedron_S2< K >	regularization ()
	returns the regularized polyhedron (closure of interior). More...

Nef_polyhedron_S2< K >	intersection (const Nef_polyhedron_S2< K > &N1)
	returns `N` \( \cap\) `N1`. More...

Nef_polyhedron_S2< K >	join (const Nef_polyhedron_S2< K > &N1)
	returns `N` \( \cup\) `N1`. More...

Nef_polyhedron_S2< K >	difference (const Nef_polyhedron_S2< K > &N1)
	returns `N` \( -\) `N1`. More...

Nef_polyhedron_S2< K >	symmetric_difference (const Nef_polyhedron_S2< K > &N1)
	returns the symmectric difference `N - T` \( \cup\) `T - N`. More...

Statistics and Integrity
Size_type	number_of_svertices ()
	returns the number of svertices. More...

Size_type	number_of_shalfedges ()
	returns the number of shalfedges. More...

Size_type	number_of_sedges ()
	returns the number of sedges. More...

Size_type	number_of_shalfloops ()
	returns the number of shalfloops. More...

Size_type	number_of_sloops ()
	returns the number of sloops. More...

Size_type	number_of_sfaces ()
	returns the number of sfaces. More...

Size_type	number_of_sface_cycles ()
	returns the number of sface cycles. More...

Size_type	number_of_connected_components ()
	calculates the number of connected components of `P`. More...

void	print_statistics (std::ostream &os=std::cout)
	print the statistics of `P`: the number of vertices, edges, and faces. More...

void	check_integrity_and_topological_planarity (bool faces=true)
	checks the link structure and the genus of `P`. More...

Iteration
bool	has_shalfloop () const
	The list of all objects can be accessed via iterator ranges. More...

SHalfloop_const_handle	shalfloop () const
	returns access to the sloop. More...

Member Typedef Documentation

◆ Mark

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::Mark

attributes of objects (vertices, edges, faces).

◆ Object_handle

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::Object_handle

a generic handle to an object of the underlying plane map.

The kind of object (vertex, halfedge, face) can be determined and the object can be assigned to a corresponding handle by the three functions:

bool assign(Vertex_const_handle& h, Object_handle)
bool assign(Halfedge_const_handle& h, Object_handle)
bool assign(Face_const_handle& h, Object_handle)

where each function returns true iff the assignment to h was done.

◆ SFace_const_handle

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SFace_const_handle

non-mutable handle to sface.

◆ SFace_const_iterator

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SFace_const_iterator

non-mutable iterator over all sfaces.

◆ SFace_cycle_const_iterator

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SFace_cycle_const_iterator

iterating all sface cycles of an sface f.

The iterator has method bool is_svertex(), bool is_shalfedge(), bool is_shalfloop(), and can be converted to the corresponding handles SVertex_const_handle, SHalfedge_const_handle, or SHalfloop_const_handle.

◆ SHalfedge_around_sface_const_circulator

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SHalfedge_around_sface_const_circulator

circulating the sface cycle of an sface f.

◆ SHalfedge_around_svertex_const_circulator

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SHalfedge_around_svertex_const_circulator

circulating the adjacency list of an svertex v.

◆ SHalfedge_const_handle

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SHalfedge_const_handle

non-mutable handle to shalfedge.

◆ SHalfedge_const_iterator

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SHalfedge_const_iterator

non-mutable iterator over all shalfedges.

◆ SHalfloop_const_handle

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SHalfloop_const_handle

non-mutable handle to shalfloop.

◆ SHalfloop_const_iterator

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SHalfloop_const_iterator

non-mutable iterator over all shalfloops.

◆ size_type

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::size_type

size type

◆ SVertex_const_handle

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SVertex_const_handle

non-mutable handle to svertex.

◆ SVertex_const_iterator

template<typename Traits >

typedef unspecified_type CGAL::Nef_polyhedron_S2< Traits >::SVertex_const_iterator

non-mutable iterator over all svertices.

Member Enumeration Documentation

◆ Boundary

template<typename Traits >

enum CGAL::Nef_polyhedron_S2::Boundary

construction selection.

Enumerator
EXCLUDED
INCLUDED

◆ Content

template<typename Traits >

enum CGAL::Nef_polyhedron_S2::Content

construction selection.

Enumerator
EMPTY
COMPLETE

Constructor & Destructor Documentation

◆ Nef_polyhedron_S2() [1/3]

template<typename Traits >

CGAL::Nef_polyhedron_S2< Traits >::Nef_polyhedron_S2 ( Content sphere = EMPTY )

creates an instance N of type Nef_polyhedron_S2<K> and initializes it to the empty set if sphere == EMPTY and to the whole sphere if sphere == COMPLETE.

◆ Nef_polyhedron_S2() [2/3]

template<typename Traits >

CGAL::Nef_polyhedron_S2< Traits >::Nef_polyhedron_S2	(	Sphere_circle	c,
		Boundary	circle = `INCLUDED`
	)

creates a Nef polyhedron N containing the half-sphere left of c including c if circle==INCLUDED, excluding c if circle==EXCLUDED.

◆ Nef_polyhedron_S2() [3/3]

template<typename Traits >

template<class Forward_iterator >

CGAL::Nef_polyhedron_S2< Traits >::Nef_polyhedron_S2	(	Forward_iterator	first,
		Forward_iterator	beyond,
		Boundary	b = `INCLUDED`
	)

creates a Nef polyhedron N from the set of sphere segments in the iterator range [first,beyond).

If the set of sphere segments is a simple polygon that separates the sphere surface into two regions, then the polygonal region that is left of the segment *first is selected. The polygonal region includes its boundary if b = INCLUDED and excludes the boundary otherwise. Forward_iterator has to be an iterator with value type Sphere_segment.

Member Function Documentation

◆ boundary()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::boundary ( )

returns the boundary of N.

◆ check_integrity_and_topological_planarity()

template<typename Traits >

void CGAL::Nef_polyhedron_S2< Traits >::check_integrity_and_topological_planarity ( bool faces = true )

checks the link structure and the genus of P.

◆ clear()

template<typename Traits >

void CGAL::Nef_polyhedron_S2< Traits >::clear ( Content plane = EMPTY )

makes N the empty set if plane == EMPTY and the full plane if plane == COMPLETE.

◆ closure()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::closure ( )

returns the closure of N.

◆ complement()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::complement ( )

returns the complement of N in the plane.

◆ contained_in_boundary()

template<typename Traits >

bool CGAL::Nef_polyhedron_S2< Traits >::contained_in_boundary ( Object_handle h )

returns true iff the object h is contained in the \( 1\)-skeleton of N.

◆ contains()

template<typename Traits >

bool CGAL::Nef_polyhedron_S2< Traits >::contains ( Object_handle h )

returns true iff the object h is contained in the set represented by N.

◆ difference()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::difference ( const Nef_polyhedron_S2< K > & N1 )

returns N \( -\) N1.

◆ has_shalfloop()

template<typename Traits >

bool CGAL::Nef_polyhedron_S2< Traits >::has_shalfloop ( ) const

The list of all objects can be accessed via iterator ranges.

For comfortable iteration we also provide iterations macros. The iterator range access operations are of the following kind:

SVertex_iterator svertices_begin()/svertices_end()
SHalfedge_iterator shalfedges_begin()/shalfedges_end()
SHalfloop_iterator shalfloops_begin()/shalfloops_end()
SFace_iterator sfaces_begin()/sfaces_end()

The macros are then

CGAL_forall_svertices(v,M),
CGAL_forall_shalfedges(e,M),
CGAL_forall_sfaces(f,M),
CGAL_forall_sface_cycles_of(fc,F)

where M is a sphere map and F is a sface.

returns true iff there is a shalfloop.

◆ interior()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::interior ( )

returns the interior of N.

◆ intersection()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::intersection ( const Nef_polyhedron_S2< K > & N1 )

returns N \( \cap\) N1.

◆ is_empty()

template<typename Traits >

bool CGAL::Nef_polyhedron_S2< Traits >::is_empty ( )

returns true if N is empty, false otherwise.

◆ is_sphere()

template<typename Traits >

bool CGAL::Nef_polyhedron_S2< Traits >::is_sphere ( )

returns true if N is the whole sphere, false otherwise.

◆ join()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::join ( const Nef_polyhedron_S2< K > & N1 )

returns N \( \cup\) N1.

◆ locate()

template<typename Traits >

Object_handle CGAL::Nef_polyhedron_S2< Traits >::locate ( const Sphere_point & p )

returns a generic handle h to an object (face, halfedge, vertex) of the underlying plane map that contains the point p in its relative interior.

The point p is contained in the set represented by N if N.contains(h) is true. The location mode flag m allows one to choose between different point location strategies.

◆ number_of_connected_components()

template<typename Traits >

Size_type CGAL::Nef_polyhedron_S2< Traits >::number_of_connected_components ( )

calculates the number of connected components of P.

◆ number_of_sedges()

template<typename Traits >

Size_type CGAL::Nef_polyhedron_S2< Traits >::number_of_sedges ( )

returns the number of sedges.

◆ number_of_sface_cycles()

template<typename Traits >

Size_type CGAL::Nef_polyhedron_S2< Traits >::number_of_sface_cycles ( )

returns the number of sface cycles.

◆ number_of_sfaces()

template<typename Traits >

Size_type CGAL::Nef_polyhedron_S2< Traits >::number_of_sfaces ( )

returns the number of sfaces.

◆ number_of_shalfedges()

template<typename Traits >

Size_type CGAL::Nef_polyhedron_S2< Traits >::number_of_shalfedges ( )

returns the number of shalfedges.

◆ number_of_shalfloops()

template<typename Traits >

Size_type CGAL::Nef_polyhedron_S2< Traits >::number_of_shalfloops ( )

returns the number of shalfloops.

◆ number_of_sloops()

template<typename Traits >

Size_type CGAL::Nef_polyhedron_S2< Traits >::number_of_sloops ( )

returns the number of sloops.

◆ number_of_svertices()

template<typename Traits >

Size_type CGAL::Nef_polyhedron_S2< Traits >::number_of_svertices ( )

returns the number of svertices.

◆ print_statistics()

template<typename Traits >

void CGAL::Nef_polyhedron_S2< Traits >::print_statistics ( std::ostream & os = std::cout )

print the statistics of P: the number of vertices, edges, and faces.

◆ ray_shoot()

template<typename Traits >

Object_handle CGAL::Nef_polyhedron_S2< Traits >::ray_shoot	(	const Sphere_point &	p,
		const Sphere_direction &	d
	)

returns a handle h with N.contains(h) that can be converted to a Vertex_/Halfedge_/Face_const_handle as described above.

The object returned is intersected by the ray starting in p with direction d and has minimal distance to p. The operation returns an empty Object_handle if the ray shoot along d does not hit any object h of N with N.contains(h).

◆ ray_shoot_to_boundary()

template<typename Traits >

Object_handle CGAL::Nef_polyhedron_S2< Traits >::ray_shoot_to_boundary	(	const Sphere_point &	p,
		const Sphere_direction &	d
	)

returns a handle h that can be converted to a Vertex_/Halfedge_const_handle as described above.

The object returned is part of the \( 1\)-skeleton of N, intersected by the ray starting in p with direction d and has minimal distance to p. The operation returns an empty Object_handle if the ray shoot along d does not hit any \( 1\)-skeleton object h of N. The location mode flag m allows one to choose between different point location strategies.

◆ regularization()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::regularization ( )

returns the regularized polyhedron (closure of interior).

◆ shalfloop()

template<typename Traits >

SHalfloop_const_handle CGAL::Nef_polyhedron_S2< Traits >::shalfloop ( ) const

returns access to the sloop.

◆ symmetric_difference()

template<typename Traits >

Nef_polyhedron_S2<K> CGAL::Nef_polyhedron_S2< Traits >::symmetric_difference ( const Nef_polyhedron_S2< K > & N1 )

returns the symmectric difference N - T \( \cup\) T - N.

Definition

template<typename Traits> class CGAL::Nef_polyhedron_S2< Traits >

Classes

Types

Creation

Operations

Constructive Operations

Statistics and Integrity

Iteration

Member Typedef Documentation

◆ Mark

◆ Object_handle

◆ SFace_const_handle

◆ SFace_const_iterator

◆ SFace_cycle_const_iterator

◆ SHalfedge_around_sface_const_circulator

◆ SHalfedge_around_svertex_const_circulator

◆ SHalfedge_const_handle

◆ SHalfedge_const_iterator

◆ SHalfloop_const_handle

◆ SHalfloop_const_iterator

◆ size_type

◆ SVertex_const_handle

◆ SVertex_const_iterator

Member Enumeration Documentation

◆ Boundary

◆ Content

Constructor & Destructor Documentation

◆ Nef_polyhedron_S2() [1/3]

◆ Nef_polyhedron_S2() [2/3]

◆ Nef_polyhedron_S2() [3/3]

Member Function Documentation

◆ boundary()

◆ check_integrity_and_topological_planarity()

◆ clear()

◆ closure()

◆ complement()

◆ contained_in_boundary()

◆ contains()

◆ difference()

◆ has_shalfloop()

◆ interior()

◆ intersection()

◆ is_empty()

◆ is_sphere()

◆ join()

◆ locate()

◆ number_of_connected_components()

◆ number_of_sedges()

◆ number_of_sface_cycles()

◆ number_of_sfaces()

◆ number_of_shalfedges()

◆ number_of_shalfloops()

◆ number_of_sloops()

◆ number_of_svertices()

◆ print_statistics()

◆ ray_shoot()

◆ ray_shoot_to_boundary()

◆ regularization()

◆ shalfloop()

◆ symmetric_difference()

template<typename Traits>
class CGAL::Nef_polyhedron_S2< Traits >