
An arrangement induced
by 23 ellipsoids in degenerate position on a base ellipsoid. 
Abstract
We introduce a general framework for processing a set of curves
defined on a continuous twodimensional parametric surface, while
sweeping the parameter space. We can handle planes, cylinders,
spheres, tori, and surfaces homeomorphic to them. A major goal of
our work is to maximize code reuse by generalizing the prevalent
sweepline paradigm and its implementation so that it can be employed
on a large class of surfaces and curves embedded on them. We have
realized our approach as a prototypical CGAL package.
We present experimental results for two concrete adaptations of the
framework for: (i) arrangements of arcs of great circles embedded on
a sphere, and (ii) arrangements of intersection curves between quadric
surfaces embedded on a quadric.
The TopologyTraits Concept
In previous CGAL versions, planar arrangements used to be
represented by the Arrangement_2 class
template. This template has two parameters: the first is a
geometrytraits class, which must be a model of the geometrytraits
model, and the other is a class that represents a DCEL
structure.
We now introduce a class template named
Arrangement_on_surface_2, which
represents an arrangement on an arbitrary surface. For backward
compatibility, the geometrytraits class maintains the same
interface. However, its predicates related to x and
y should
interpreted in the twodimensional parameter space that defines the
surface. The second template parameter is a topologytraits class,
which defines the specific manner the arrangement is represented as
a DCEL structure. We next give a more detailed
description on the requirements from the topologytraits class.
First, the topologytraits class must define a nested Dcel
type, which corresponds to the DCEL class used to
represent the arrangement. In addition it must define visitors
that perform certain tasks. The most important visitors are:
 Construction sweepline visitor
 A sweepline visitor class that can construct the arrangement of
a set of curves from scratch.
 Insertion sweepline visitor
 A sweepline visitor class that can insert a set of curves into
a nonempty arrangement.
 Overlay sweepline visitor
 A sweepline visitor class that constructs a new arrangement
corresponding to the overlay of two input arrangements.
 Insertion zone visitor
 Used to insert a single curve into an existing arrangement by
computing its zone. Like the sweepline algorithm, the
zonecomputation algorithm is also implemented in a generic fashion
and its output is determined by a visitor class.
The fact that the visitor classes are defined by the topologytraits
classes makes it possible to support generic functions that operate
on the Arrangement_on_surface_2 class. For example, the
function insert_curves(arr, begin, end) accepts an
arrangement instance arr and a range of curves defined by
[begin, end). If the arrangement is empty, it uses the
construction sweepline visitor to sweep over the input curves and
construct their arrangement. Otherwise, it uses the insertion
sweepline visitor to insert them into the existing arrangement.
There are usually several alternatives for the actual
DCEL representation of an arrangement on a
specific surface.
 
Different DCEL representations
for the same arrangement 

The topologytraits class encapsulates the actual DCEL
representation of the arrangement. It provides access to
the DCEL class, such that the
Arrangement_on_surface_2 class can directly
update DCEL records with no boundary conditions (i.e.,
all vertices and edges related to points and curves in the
augmented parameter space).
The topologytraits class is however
responsible for handling the DCEL records that represents
the surface boundaries: infinity, curves of discontinuity (identification),
and singularity (contraction) points. To do so, it provides the following
functionality:
 Initialize
 Construct a DCEL structure that represents an
empty arrangement.
 Place boundary vertex
 Locate the DCEL vertex to which a given curve
object with a boundary condition will be assigned, if existing. Otherwise
it returns NULL.
 Notify on boundary vertex creation
 This function is used to notify the topological traits that a new
DCEL vertex has been created which carries a boundary
condition. This way it is possible to keep the internal objects of the
topological traits uptodate.
 Locate around boundary vertex
 For a given DCEL vertex, this functions returns
the predecessor halfedge which identifies where to insert a given curve
with a boundary condition. If may return NULL, if there is no such.
 Is redundant
 Determine whether a given vertex with a boundary condition becomes
redundant. For example, a vertex that lie on a fictitious halfedge
becomes redundant after one of its nonfictitious incident halfedges
is deleted (typically it is only incident to two fictitious
halfedges), or consider the case where a vertex representing
a contraction point becomes isolated.
 Remove redundant vertex
 Remove a redundant vertex from the DCEL structure.
 Is perimetric path
 Determine whether a sequence of halfedges (given by first
and last halfedge) forms a perimetric path, i.e., crosses
an existing curve of identification an odd number of times.
 Boundaries of same face
 Check whether two given perimetric loops (each indicated by
an halfedge) form outer boundaries of the same incident
face.
Links
Contact
Eric Berberich



Efi Fogel



Dan Halperin



Kurt Mehlhorn



Ron Wein



Site is maintained by
Efi Fogel.
Last modified: July 19 2007.