2D Boolean Operations on Nef Polygons Embedded on the Sphere

*Peter Hachenberger and Lutz Kettner*

17.1 | Introduction | ||||

17.2 | Restricted Spherical Geometry | ||||

17.3 | Example Programs | ||||

17.3.1 First Example | |||||

17.3.2 Construction and Combinations | |||||

17.3.3 Exploration | |||||

17.3.4 Point Location | |||||

17.3.5 Visualization |

Nef polyhedra are defined as a subset of the d-dimensional space obtained by a finite number of set complement and set intersection operations on halfspaces.

Due to the fact that all other binary set operations like union, difference and symmetric difference can be reduced to intersection and complement calculations, Nef polyhedra are also closed under those operations. Also, Nef polyhedra are closed under topological unary set operations. Given a Nef polyhedron one can determine its interior, its boundary, and its closure.

**Figure 17.1: **Two spherical Nef polyhedra. A closed halfspace on the left
and a complex polyhedron on the right. The different colors indicate
selected and unselected regions, lines and points.

Additionally, a d-dimensional Nef polyhedron has the property, that its boundary is a (d-1)-dimensional Nef polyhedron. This property can be used as a way to represent 3-dimensional Nef polyhedra by means of planar Nef polyhedra. This is done by intersecting the neighborhood of a vertex in a 3D Nef polyhedron with an $$-sphere. The result is a planar Nef polyhedron embedded on the sphere.

The intersection of a halfspace going through the center of the $$-sphere, with the $$-sphere, results in a halfsphere which is bounded by a great circle. A binary operation of two halfspheres cuts the great circles into great arcs.

The incidence structure of planar Nef polyhedra can be reused. The items
are denoted as $$*svertex*, $$*shalfedge* and $$*sface*, analogous
to their counterparts in *Nef_polyhedron_S2*. Additionally, there is the
*shalfloop* reprsenting the great circles. The incidences are
illustrated in the figure above.

We introduce geometric objects that are part of the spherical surface
$$*S _{2}* and operations on them. We define types

Note that we have to consider special geometric properties of the
objects. For example two points that are part of a great circle define
two *Sphere_segment*s, and two arbitrary *Sphere_segment*s can
intersect in two points.

If we restrict our geometric objects to a so-called perfect hemisphere
of $$*S _{2}*

In this first example *Nef_polyhedron_S2* is parametrized with a CGAL
Kernel as traits class. The types comprising the spherical geometry can be
retrieved from the type *Nef_polyhedron_S2<Traits>* as is done in the example
with the type
*Sphere_circle*. Then three Nef polyhedra are created: $$*N1* is a halfsphere
including the boundary, $$*N2* is another halfsphere without the boundary, and
$$*N3* is the intersection of $$*N1* and $$*N2*.

File:examples/Nef_S2/nef_s2_simple.cpp

#include <CGAL/Gmpz.h> #include <CGAL/Homogeneous.h> #include <CGAL/Nef_polyhedron_S2.h> typedef CGAL::Gmpz RT; typedef CGAL::Homogeneous<RT> Kernel; typedef CGAL::Nef_polyhedron_S2<Kernel> Nef_polyhedron; typedef Nef_polyhedron::Sphere_circle Sphere_circle; int main() { Nef_polyhedron N1(Sphere_circle(1,0,0)); Nef_polyhedron N2(Sphere_circle(0,1,0), Nef_polyhedron::EXCLUDED); Nef_polyhedron N3 = N1 * N2; return 0; }

Th example shows the different types of constructors: $$*N1* is the complete
sphere, $$*N2* is a halfsphere which includes the boundary, $$*N3* is created
with the copy constructor, $$*N4* is created as an arrangement of a set
of *Sphere_segments*, and $$*N5* is created as the empty set.

The example also shows the use of unary set operations, binary operations,
and binary predicates: $$*N3* is defined as the complement of $$*N2*, $$*N1* is
compared with the union of $$*N2* and $$*N3*, $$*N5* is united with $$*N2* and then
intersected with $$*N4*. At last, it is tested if $$*N5* is a subset of $$*N2* and
if $$*N5* is not equal to $$*N4*.

File:examples/Nef_S2/nef_s2_construction.cpp

#include <CGAL/Gmpz.h> #include <CGAL/Homogeneous.h> #include <CGAL/Nef_polyhedron_S2.h> typedef CGAL::Gmpz RT; typedef CGAL::Homogeneous<RT> Kernel; typedef CGAL::Nef_polyhedron_S2<Kernel> Nef_polyhedron; typedef Nef_polyhedron::Sphere_point Sphere_point; typedef Nef_polyhedron::Sphere_segment Sphere_segment; typedef Nef_polyhedron::Sphere_circle Sphere_circle; int main() { Nef_polyhedron N1(Nef_polyhedron::COMPLETE); Sphere_circle c(1,1,1); // c : x + y + z = 0 Nef_polyhedron N2(c, Nef_polyhedron::INCLUDED); Nef_polyhedron N3(N2.complement()); CGAL_assertion(N1 == N2.join(N3)); Sphere_point p1(1,0,0), p2(0,1,0), p3(0,0,1); Sphere_segment s1(p1,p2), s2(p2,p3), s3(p3,p1); Sphere_segment triangle[3] = { s1, s2, s3 }; Nef_polyhedron N4(triangle, triangle+3); Nef_polyhedron N5; N5 += N2; N5 = N5.intersection(N4); CGAL_assertion(N5 <= N2 && N5 != N4); return 0; }

By recursively composing binary and unary operations one can end with
a very complex rectilinear structure. *Nef_polyhedron_S2* allows
read-only exploration of the structure.

In the following example, a random *Nef_polyhedron_S2 S* created from
*n* halfspheres is explored. Each sface is composed of one outer
sface cycles and an arbitrary number of inner sfaces cycles. The outer cycle
is either an shalfloop or a cycle of shalfedges. An inner cycles additionally
can be an isolated vertex. The example shows how to get the entry item *it*
to all sface cycles of an sface *sf* and how to find out what type of item
it is.

The macro *CGAL_forall_sface_cycles_of* is equivalent to a for-loop
on the range *[sf->sface_cycles_begin(), sf->sface_cycles_end())*. An
*SFace_cycle_const_iterator* either represents a *SVertex_const_handle*,
a *SHalfede_const_handle* or a *SHalfloop_const_handle*. In order
to find out which handle type is represented, the functions
*is_svertex()*, *is_shafledge()* and *is_shalfloop()* are provided.
Afterwards the iterator can be casted to the proper handle type.

File:examples/Nef_S2/nef_s2_exploration.cpp

#include <CGAL/Gmpq.h> #include <CGAL/Cartesian.h> #include <CGAL/Nef_polyhedron_S2.h> #include <CGAL/Nef_S2/create_random_Nef_S2.h> typedef CGAL::Gmpq FT; typedef CGAL::Cartesian<FT> Kernel; typedef CGAL::Nef_polyhedron_S2<Kernel> Nef_polyhedron_S2; typedef Nef_polyhedron_S2::SVertex_const_handle SVertex_const_handle; typedef Nef_polyhedron_S2::SHalfedge_const_handle SHalfedge_const_handle; typedef Nef_polyhedron_S2::SHalfloop_const_handle SHalfloop_const_handle; typedef Nef_polyhedron_S2::SFace_const_iterator SFace_const_iterator; typedef Nef_polyhedron_S2::SFace_cycle_const_iterator SFace_cycle_const_iterator; int main() { Nef_polyhedron_S2 S; CGAL::create_random_Nef_S2(S,5); int i=0; SFace_const_iterator sf; CGAL_forall_sfaces(sf,S) { SFace_cycle_const_iterator it; std::cout << "the sface cycles of sface " << i++; std::cout << " start with an " << std::endl; CGAL_forall_sface_cycles_of(it,sf) { if (it.is_svertex()) { std::cout << " svertex at position "; std::cout << SVertex_const_handle(it)->point() << std::endl; } else if (it.is_shalfedge()) { std::cout << " shalfedge from "; std::cout << SHalfedge_const_handle(it)->source()->point() << " to "; std::cout << SHalfedge_const_handle(it)->target()->point() << std::endl; } else if (it.is_shalfloop()) { std::cout << " shalfloop lying in the plane "; std::cout << SHalfloop_const_handle(it)->circle() << std::endl; } else std::cout << "something is wrong" << std::endl; } } return 0; }

Using the *locate* function, it is possible to retrive an item at a
certain location on the sphere. In the following example, the item at
location *Sphere_point(1,0,0)* in a random *Nef_polyhedron_S2* is
retrieved. *locate* returns an instance of type *Object_handle*, which
is a container for any handle type. Here, it either a
*SVertex_const_handle*, a *SHalfedge_const_handle*,
a *SHafloop_const_handle* or a *SFace_const_handle*. The function
*CGAL::assign* performs the cast operation and returns a boolean which
indicates whether the cast was successful or not.

File:examples/Nef_S2/nef_s2_point_location.cpp

#include <CGAL/Gmpq.h> #include <CGAL/Cartesian.h> #include <CGAL/Nef_polyhedron_S2.h> #include <CGAL/Nef_S2/create_random_Nef_S2.h> typedef CGAL::Gmpq FT; typedef CGAL::Cartesian<FT> Kernel; typedef CGAL::Nef_polyhedron_S2<Kernel> Nef_polyhedron_S2; typedef Nef_polyhedron_S2::SVertex_const_handle SVertex_const_handle; typedef Nef_polyhedron_S2::SHalfedge_const_handle SHalfedge_const_handle; typedef Nef_polyhedron_S2::SHalfloop_const_handle SHalfloop_const_handle; typedef Nef_polyhedron_S2::SFace_const_handle SFace_const_handle; typedef Nef_polyhedron_S2::Object_handle Object_handle; typedef Nef_polyhedron_S2::Sphere_point Sphere_point; int main() { Nef_polyhedron_S2 S; CGAL::create_random_Nef_S2(S,5); SVertex_const_handle sv; SHalfedge_const_handle se; SHalfloop_const_handle sl; SFace_const_handle sf; Object_handle o = S.locate(Sphere_point(1,0,0)); if(CGAL::assign(sv,o)) std::cout << "Locating svertex" << std::endl; else if(CGAL::assign(se,o)) std::cout << "Locating shalfedge" << std::endl; else if(CGAL::assign(sl,o)) std::cout << "Locating shalfloop" << std::endl; else if(CGAL::assign(sf,o)) std::cout << "Locating sface" << std::endl; else { std::cout << "something wrong" << std::endl; return 1; } return 0; }

*Nef_polyhedron_S2* provides an interface for OpenGL visualization via a
Qt widget. The usage is shown in the following example:

File:demo/Nef_S2/nef_S2.cpp

#include <CGAL/basic.h> #include <CGAL/Gmpz.h> #include <CGAL/Homogeneous.h> #include <CGAL/Nef_polyhedron_S2.h> #include <CGAL/Nef_S2/create_random_Nef_S2.h> #include <CGAL/IO/Qt_widget_Nef_S2.h> #include <qapplication.h> typedef CGAL::Gmpz RT; typedef CGAL::Homogeneous<RT> Kernel; typedef CGAL::Nef_polyhedron_S2<Kernel> Nef_polyhedron_S2; int main(int argc, char* argv[]) { Nef_polyhedron_S2 S; create_random_Nef_S2(S,5); QApplication a(argc, argv); CGAL::Qt_widget_Nef_S2<Nef_polyhedron_S2>* w = new CGAL::Qt_widget_Nef_S2<Nef_polyhedron_S2>(S); a.setMainWidget(w); w->show(); return a.exec(); }

^{1} |
A perfect hemisphere of $$S is an open half-sphere
plus an open half-circle in the boundary of the open half-sphere
plus one endpoint of the half-circle.
_{2} |