CGAL 4.7  2D Boolean Operations on Nef Polygons Embedded on the Sphere

#include <CGAL/Nef_polyhedron_S2.h>
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
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 halfspaces 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_Windowstream.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.
Classes  
class  SFace 
Figures figureNefS2SVertexIncidences and figureNefS2SHalfloopIncidences illustrate the incidences of an sface. 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 sloop is a great circle on a sphere. More...  
class  Sphere_circle 
An object c of type Sphere_circle is an oriented great circle on the surface of a unit sphere. More...  
class  Sphere_point 
An object p of type Sphere_point<R> is a point on the surface of a unit sphere. More...  
class  Sphere_segment 
An object s of type Sphere_segment is a segment in the surface of a unit sphere that is part of a great circle trough the origin. More...  
class  SVertex 
Figure figureNefS2SVertexIncidences illustrates the incidence of a svertex on a sphere map. More...  
Types  
enum  Boundary { EXCLUDED, INCLUDED } 
construction selection. More...  
enum  Content { EMPTY, COMPLETE } 
construction selection. More...  
typedef unspecified_type  SVertex_const_handle 
nonmutable handle to svertex.  
typedef unspecified_type  SHalfedge_const_handle 
nonmutable handle to shalfedge.  
typedef unspecified_type  SHalfloop_const_handle 
nonmutable handle to shalfloop.  
typedef unspecified_type  SFace_const_handle 
nonmutable handle to sface.  
typedef unspecified_type  SVertex_const_iterator 
nonmutable iterator over all svertices.  
typedef unspecified_type  SHalfedge_const_iterator 
nonmutable iterator over all shalfedges.  
typedef unspecified_type  SHalfloop_const_iterator 
nonmutable iterator over all shalfloops.  
typedef unspecified_type  SFace_const_iterator 
nonmutable iterator over all sfaces.  
typedef unspecified_type  SHalfedge_around_svertex_const_circulator 
circulating the adjacency list of an svertex v .  
typedef unspecified_type  SHalfedge_around_sface_const_circulator 
circulating the sface cycle of an sface f .  
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).  
typedef unspecified_type  size_type 
size type  
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 .  
Nef_polyhedron_S2 (Sphere_circle c, Boundary circle=INCLUDED)  
creates a Nef polyhedron N containing the halfsphere left of c including c if circle==INCLUDED , excluding c if circle==EXCLUDED .  
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 .  
bool  is_empty () 
returns true if N is empty, false otherwise.  
bool  is_sphere () 
returns true if N is the whole sphere, false otherwise.  
bool  contains (Object_handle h) 
returns true iff the object h is contained in the set represented by N .  
bool  contained_in_boundary (Object_handle h) 
returns true iff the object h is contained in the \( 1\)skeleton of N .  
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 There are also the corresponding modification operations There are also comparison operations like  
Nef_polyhedron_S2< K >  complement () 
returns the complement of N in the plane.  
Nef_polyhedron_S2< K >  interior () 
returns the interior of N .  
Nef_polyhedron_S2< K >  closure () 
returns the closure of N .  
Nef_polyhedron_S2< K >  boundary () 
returns the boundary of N .  
Nef_polyhedron_S2< K >  regularization () 
returns the regularized polyhedron (closure of interior).  
Nef_polyhedron_S2< K >  intersection (const Nef_polyhedron_S2< K > &N1) 
returns N \( \cap\) N1 .  
Nef_polyhedron_S2< K >  join (const Nef_polyhedron_S2< K > &N1) 
returns N \( \cup\) N1 .  
Nef_polyhedron_S2< K >  difference (const Nef_polyhedron_S2< K > &N1) 
returns N \( \) N1 .  
Nef_polyhedron_S2< K >  symmetric_difference (const Nef_polyhedron_S2< K > &N1) 
returns the symmectric difference N  T \( \cup\) T  N .  
Statistics and Integrity  
Size_type  number_of_svertices () 
returns the number of svertices.  
Size_type  number_of_shalfedges () 
returns the number of shalfedges.  
Size_type  number_of_sedges () 
returns the number of sedges.  
Size_type  number_of_shalfloops () 
returns the number of shalfloops.  
Size_type  number_of_sloops () 
returns the number of sloops.  
Size_type  number_of_sfaces () 
returns the number of sfaces.  
Size_type  number_of_sface_cycles () 
returns the number of sface cycles.  
Size_type  number_of_connected_components () 
calculates the number of connected components of P .  
void  print_statistics (std::ostream &os=std::cout) 
print the statistics of P : the number of vertices, edges, and faces.  
void  check_integrity_and_topological_planarity (bool faces=true) 
checks the link structure and the genus of P .  
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.  
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.
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
.
enum CGAL::Nef_polyhedron_S2::Boundary 
enum CGAL::Nef_polyhedron_S2::Content 
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
.
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.
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.
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)
.
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.