CGAL::Arrangement_2<Traits,Dcel>
Definition
An object arr of the class Arrangement_2<Traits,Dcel> represents the
planar subdivision induced by a set of -monotone curves and isolated
points into maximally connected cells. The arrangement is represented as
a doubly-connected edge-list (DCEL) such that each DCEL vertex
is associated with a point of the plane and each edge is
associated with an -monotone curve whose interior is disjoint from all
other edges and vertices. Recall that an arrangement
edge is always comprised of a pair of twin DCEL halfedges.
The Arrangement_2<Traits,Dcel> template has two parameters:
- The Traits template-parameter should be instantiated with
a model of the ArrangementBasicTraits_2 concept. The traits
class defines the types of -monotone curves and two-dimensional
points, namely X_monotone_curve_2 and Point_2,
respectively, and supports basic geometric predicates on them.
- The Dcel template-parameter should be instantiated with
a class that is a model of the ArranagementDcel concept. The
value of this parameter is by default
Arr_default_dcel<Traits>.
The available traits classes and DCEL classes are described below.
#include <CGAL/Arrangement_2.h>
Types
|
Arrangement_2<Traits,Dcel>::Traits_2
|
|
the traits class in use.
|
|
Arrangement_2<Traits,Dcel>::Dcel
|
|
the DCEL representation of the arrangement.
|
|
typedef typename Traits_2::Point_2
|
|
Point_2;
|
the point type, as defined by the traits class.
|
|
typedef typename Traits_2::X_monotone_curve_2
|
|
X_monotone_curve_2;
|
the -monotone curve type, as defined by the traits class.
|
|
|
typedef typename Dcel::Size
|
Size;
|
the size type (equivalent to size_t).
|
|
Arrangement_2<Traits,Dcel>::Vertex
|
|
represents a -dimensional cell in the subdivision.
A vertex is always associated with a point.
|
|
Arrangement_2<Traits,Dcel>::Halfedge
|
|
represents (together with its twin - see below)
a -dimensional cell in the subdivision.
A halfedge is always associated with an -monotone curve.
|
|
Arrangement_2<Traits,Dcel>::Face
|
|
represents a -dimensional cell in the subdivision.
|
The following handles, iterators, and circulators all have respective
constant counterparts (for example, in addition to Vertex_iterator
the type Vertex_const_iterator is also defined).
See [MS96] for a discussion of constant versus mutable
iterator types. The mutable types are assignable to their constant
counterparts.
Vertex_iterator, Halfedge_iterator, and
Face_iterator are equivalent to the respective handle types (namely,
Vertex_handle, Halfedge_handle, and Face_handle). Thus,
wherever the handles appear in function parameter lists, the respective
iterators can be passed as well.
|
Arrangement_2<Traits,Dcel>::Vertex_handle
|
|
a handle for an arrangement vertex.
|
|
Arrangement_2<Traits,Dcel>::Halfedge_handle
|
|
a handle for a halfedge.
The halfedge and its twin form together an arrangement edge.
|
|
Arrangement_2<Traits,Dcel>::Face_handle
|
|
a handle for an arrangement face.
|
|
|
Arrangement_2<Traits,Dcel>::Vertex_iterator
|
|
a bidirectional iterator over the
vertices of the arrangement. Its value-type is Vertex.
|
|
Arrangement_2<Traits,Dcel>::Halfedge_iterator
|
|
a bidirectional iterator over the
halfedges of the arrangement. Its value-type is Halfedge.
|
|
Arrangement_2<Traits,Dcel>::Edge_iterator
|
|
a bidirectional iterator over the
edges of the arrangement. (That is, it skips every other halfedge.)
Its value-type is Halfedge.
|
|
Arrangement_2<Traits,Dcel>::Face_iterator
|
|
a bidirectional iterator over the
faces of arrangement. Its value-type is Face.
|
|
Arrangement_2<Traits,Dcel>::Unbounded_face_iterator
|
|
a bidirectional iterator over the
unbounded faces of arrangement. Its value-type is Face.
|
|
|
Arrangement_2<Traits,Dcel>::Halfedge_around_vertex_circulator
|
|
a bidirectional circulator
over the halfedges that have a given vertex as their target.
Its value-type is Halfedge.
|
|
Arrangement_2<Traits,Dcel>::Ccb_halfedge_circulator
|
|
a bidirectional circulator over the
halfedges of a CCB (connected component of the boundary).
Its value-type is Halfedge. Each
bounded face has a single CCB representing it outer boundary, and may
have several inner CCBs representing its holes.
|
|
Arrangement_2<Traits,Dcel>::Hole_iterator
|
|
a bidirectional iterator over the holes
(i.e., inner CCBs) contained inside a given face.
Its value type is Ccb_halfedge_circulator.
|
|
Arrangement_2<Traits,Dcel>::Isolated_vertex_iterator
|
|
a bidirectional iterator over the
isolated vertices contained inside a given face.
Its value type is Vertex.
|
Creation
|
Arrangement_2<Traits,Dcel> arr;
|
|
constructs an empty arrangement containing one unbounded face,
which corresponds to the entire plane.
|
|
|
Arrangement_2<Traits,Dcel> arr ( Self other);
|
|
copy constructor.
|
|
|
Arrangement_2<Traits,Dcel> arr ( Traits_2 *traits);
|
|
constructs an empty arrangement that uses the given traits
instance for performing the geometric predicates.
|
Assignment Methods
|
Self&
|
arr =
other
|
assignment operator.
|
|
|
void
|
arr.assign ( Self other)
|
assigns the contents of another arrangement.
|
|
|
void
|
arr.clear ()
|
clears the arrangement.
|
Access Functions
|
Traits_2*
|
arr.get_traits ()
|
returns the traits object used by the arrangement instance.
A const version is also available.
|
|
|
bool
|
arr.is_empty ()
|
determines whether the arrangement is empty (contains only the unbounded
face, with no vertices or edges).
|
All _begin() and _end() methods listed below also have const
counterparts, returning constant iterators instead of mutable ones:
Accessing the Arrangement Vertices:
|
Size
|
arr.number_of_vertices ()
|
returns the number of vertices in the arrangement.
|
|
|
Size
|
arr.number_of_isolated_vertices ()
|
| |
returns the total number of isolated vertices in the arrangement.
|
|
|
Vertex_iterator
|
arr.vertices_begin ()
|
returns the begin-iterator of the vertices in the arrangement.
|
|
|
Vertex_iterator
|
arr.vertices_end ()
|
returns the past-the-end iterator of the vertices in the arrangement.
|
|
|
Size
|
arr.number_of_vertices_at_infinity ()
|
| |
returns the number of arrangement vertices that lie at infinity and
are not associated with valid points. Such vertices are not considered
to be regular arrangement vertices and arr.number_of_vertices()
does not count them.
|
Accessing the Arrangement Edges:
|
Size
|
arr.number_of_halfedges ()
|
returns the number of halfedges in the arrangement.
|
|
|
Halfedge_iterator
|
arr.halfedges_begin ()
|
returns the begin-iterator of the halfedges in the arrangement.
|
|
|
Halfedge_iterator
|
arr.halfedges_end ()
|
returns the past-the-end iterator of the halfedges in the arrangement.
|
|
|
Size
|
arr.number_of_edges ()
|
returns the number of edges in the arrangement (equivalent to
arr.number_of_halfedges() / 2).
|
|
|
Edge_iterator
|
arr.edges_begin ()
|
returns the begin-iterator of the edges in the arrangement.
|
|
|
Edge_iterator
|
arr.edges_end ()
|
returns the past-the-end iterator of the edges in the arrangement.
|
Accessing the Arrangement Faces:
|
Face_handle
|
arr.unbounded_face ()
|
returns a handle for an unbounded face of the arrangement.
In case the arrangement comprises only bounded curves, there is a single
unbounded face and the function returns a handle to it. Otherwise, a
handle to an arbitrary unbounded face is returned.
|
|
|
Size
|
arr.number_of_faces ()
|
returns the number of faces in the arrangement.
|
|
|
Face_iterator
|
arr.faces_begin ()
|
returns the begin-iterator of the faces in the arrangement.
|
|
|
Face_iterator
|
arr.faces_end ()
|
returns the past-the-end iterator of the faces in the arrangement.
|
|
|
Size
|
arr.number_of_unbounded_faces ()
|
returns the number of unbounded faces in the arrangement.
Note arr.number_of_faces() also counts the unbounded faces
of the arrangement.
|
|
|
Unbounded_face_iterator
|
arr.unbounded_faces_begin ()
|
returns the begin-iterator of the unbounded faces in the arrangement.
|
|
|
Unbounded_face_iterator
|
arr.unbounded_faces_end ()
|
returns the past-the-end iterator of the unbounded faces in the
arrangement.
|
|
advanced
|
|
Casting away Constness
It is sometime necessary to convert a constant (non-mutable) handle to
a mutable handle. For example, the result of a point-location query is
a non-mutable handle for the arrangement cell containing the query point.
Assume that the query point lies on a edge, so we obtain a
Halfedge_const_handle; if we wish to use this handle and remove the
edge, we first need to cast away its ``constness''.
|
Vertex_handle
|
arr.non_const_handle ( Vertex_const_handle v)
|
| |
casts the given constant vertex handle to an equivalent mutable handle.
|
|
|
Halfedge_handle
|
arr.non_const_handle ( Halfedge_const_handle e)
|
| |
casts the given constant halfedge handle to an equivalent mutable handle.
|
|
|
Face_handle
|
arr.non_const_handle ( Face_const_handle f)
|
| |
casts the given constant face handle to an equivalent mutable handle.
|
|
advanced
|
|
Modifiers
Specialized Insertion Methods:
|
Vertex_handle
|
arr.insert_in_face_interior ( Point_2 p, Face_handle f)
|
| |
inserts the point p into the arrangement as an isolated vertex in
the interior of the face f and returns a handle for the newly
created vertex.
| Precondition: | p lies in the interior of the face f. |
|
|
|
Halfedge_handle
|
arr.insert_in_face_interior ( X_monotone_curve_2 c, Face_handle f)
|
| |
inserts the curve c that is entirely contained in the interior
of a given face f. If c is a bounded curve two new vertices
that correspond to c's endpoints are created and connected with a
newly created halfedge pair, which forms a new hole (inner component)
in the face f. If c is unbounded, at least one of the two
vertices that represents its end lies at infinity, and its creation
modifies the outer boundary of f.
The function returns a handle for one of the new halfedges
corresponding to the inserted curve, directed in lexicographic
increasing order (from left to right).
| Precondition: | c lies entirely in the interior of the face f and
is disjoint from all existing arrangement vertices and edges (in
particular, both its endpoints are not already associated with existing
arrangement vertices).
|
| Precondition: | In case c is an unbounded curve, f must be an
unbounded face. |
|
|
|
Halfedge_handle
|
arr.insert_from_left_vertex ( X_monotone_curve_2 c, Vertex_handle v)
|
| |
inserts the curve c into the arrangement, such that its left
endpoint corresponds to a given arrangement vertex. As a result, a new
vertex that correspond to c's right endpoint is created and
connected to v with a newly created halfedge pair. If c has
an unbounded right end, the new vertex lies at infinity and the
unbounded face that contains the interior of the curve is split.
The function returns a handle for one of the new halfedges corresponding
to the inserted curve, directed towards the newly created vertex -
that is, directed in lexicographic increasing order (from left to right).
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges.
|
| Precondition: | v is associated with the left endpoint of c.
|
| Precondition: | The right endpoint of c is not already associated with
an existing arrangement vertex. |
|
|
|
Halfedge_handle
|
arr.insert_from_right_vertex ( X_monotone_curve_2 c, Vertex_handle v)
|
| |
inserts the curve c into the arrangement, such that its right
endpoint corresponds to a given arrangement vertex. As a result, a new
vertex that correspond to c's left endpoint is created and
connected to v with a newly created halfedge pair. If c has
an unbounded left end, the new vertex lies at infinity and the
unbounded face that contains the interior of the curve is split.
The function returns a handle for one of the new halfedges corresponding
to the inserted curve, directed to the newly created vertex -
that is, directed in lexicographic decreasing order (from right to left).
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges.
|
| Precondition: | v is associated with the right endpoint of c.
|
| Precondition: | The left endpoint of c is not already associated with
an existing arrangement vertex. |
|
|
|
Halfedge_handle
|
arr.insert_at_vertices ( X_monotone_curve_2 c, Vertex_handle v1, Vertex_handle v2)
|
| |
inserts the curve c into the arrangement, such that both c's
endpoints correspond to existing arrangement vertices, given by v1
and v2. The function creates a new halfedge pair that connects the
two vertices, and returns a handle for the halfedge directed from v1
to v2.
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges.
|
| Precondition: | c must not be an unbounded curve.
|
| Precondition: | v1 and v2 are associated with c's endpoints.
|
| Precondition: | If v1 and v2 are already
connected by an edge, this edge represents an -monotone
curve that is interior-disjoint from c). |
|
|
|
advanced
|
|
|
Halfedge_handle
|
|
arr.insert_in_face_interior ( |
X_monotone_curve_2 c,
Halfedge_handle fict_pred1,
Halfedge_handle fict_pred2 = Halfedge_handle()) |
|
| |
inserts an unbounded curve c into the arrangement, such that c
is entirely contained within a single unbounded face of the arrangement.
fict_pred1 specifies the fictitious halfedge that should contain the
vertex at infinity that corresponds to the unbounded end of c. If
both ends of c are unbounded, fict_pred1 indicated the place
for its left end and fict_pred2 indicated a place for its right end.
The function returns a handle for one of the new halfedges directed
(lexicographically) from left to right.
| Precondition: | c is an unbounded curve disjoint from all existing
arrangement vertices and edges.
|
| Precondition: | fict_pred1 (and fict_pred2) are fictitious halfedges
that contains the unbounded end(s) of c. If both halfedges are given
they must be both incident to the same unbounded face. |
|
|
|
Halfedge_handle
|
arr.insert_from_left_vertex ( X_monotone_curve_2 c, Halfedge_handle pred)
|
| |
inserts the curve c into the arrangement, such that its left
endpoint corresponds to a given arrangement vertex. This vertex is the
target vertex of the halfedge pred, such that c is inserted
to the circular list of halfedges around pred->target() right
between pred and its successor. The function returns a handle for
one of the new halfedges directed (lexicographically) from left to right.
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges.
|
| Precondition: | pred->target() is associated with the left endpoint
of c, and c should be inserted after pred in a
clockwise order around this vertex.
|
| Precondition: | The right endpoint of c is not already associated with
an existing arrangement vertex. |
|
|
|
Halfedge_handle
|
|
arr.insert_from_left_vertex ( |
X_monotone_curve_2 c,
Halfedge_handle pred,
Halfedge_handle fict_pred) |
|
| |
inserts an unbounded curve c into the arrangement, such that its left
endpoint is bounded and corresponds to a given arrangement vertex. This
vertex is the target vertex of the halfedge pred, such that c
is inserted to the circular list of halfedges around pred->target()
right between pred and its successor. Similarly, fict_pred
specifies the fictitious halfedge that should contain the vertex at infinity
that corresponds to the unbounded right end of c.
The function returns a handle for one of the new halfedges directed
(lexicographically) from left to right.
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges. c must have a bounded left endpoint and an
unbounded right end.
|
| Precondition: | pred->target() is associated with the left endpoint
of c, and c should be inserted after pred in a
clockwise order around this vertex.
|
| Precondition: | fict_pred is a fictitious halfedge that contains the
unbounded right end of c. |
|
|
|
Halfedge_handle
|
arr.insert_from_right_vertex ( X_monotone_curve_2 c, Halfedge_handle pred)
|
| |
inserts the curve c into the arrangement, such that its right
endpoint corresponds to a given arrangement vertex. This vertex is the
target vertex of the halfedge pred, such that c is inserted
to the circular list of halfedges around pred->target() right
between pred and its successor. The function returns a handle for
one of the new halfedges directed (lexicographically) from right to left.
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges.
|
| Precondition: | pred->target() is associated with the right endpoint
of c, and c should be inserted after pred in a
clockwise order around this vertex.
|
| Precondition: | The left endpoint of c is not already associated with
an existing arrangement vertex. |
|
|
|
Halfedge_handle
|
|
arr.insert_from_right_vertex ( |
X_monotone_curve_2 c,
Halfedge_handle pred,
Halfedge_handle fict_pred) |
|
| |
inserts an unbounded curve c into the arrangement, such that its right
endpoint is bounded and corresponds to a given arrangement vertex. This
vertex is the target vertex of the halfedge pred, such that c
is inserted to the circular list of halfedges around pred->target()
right between pred and its successor. Similarly, fict_pred
specifies the fictitious halfedge that should contain the vertex at infinity
that corresponds to the unbounded left end of c.
The function returns a handle for one of the new halfedges directed
(lexicographically) from right to left.
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges. c must have a bounded right endpoint and an
unbounded left end.
|
| Precondition: | pred->target() is associated with the right endpoint
of c, and c should be inserted after pred in a
clockwise order around this vertex.
|
| Precondition: | fict_pred is a fictitious halfedge that contains the
unbounded left end of c. |
|
|
|
Halfedge_handle
|
arr.insert_at_vertices ( X_monotone_curve_2 c, Halfedge_handle pred1, Vertex_handle v2)
|
| |
inserts the curve c into the arrangement, such that both c's
endpoints correspond to existing arrangement vertices, given by
pred1->target() and v2. The function creates a new halfedge
pair that connects the two vertices (where the corresponding halfedge is
inserted right between pred1 and its successor around pred1's
target vertex) and returns a handle for the halfedge directed from
pred1->target() to v2.
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges.
|
| Precondition: | pred1->target() and v2 are associated with
c's endpoints.
|
| Precondition: | If pred1->target and v2 are already connected
by an edge, this edge represents an -monotone curve that
is interior-disjoint from c). |
|
|
|
Halfedge_handle
|
arr.insert_at_vertices ( X_monotone_curve_2 c, Halfedge_handle pred1, Halfedge_handle pred2)
|
| |
inserts the curve c into the arrangement, such that both c's
endpoints correspond to existing arrangement vertices, given by
pred1->target() and pred2->target(). The function creates a
new halfedge pair that connects the two vertices (with pred1 and
pred2 indicate the exact place for these halfedges around the two
target vertices) and returns a handle for the halfedge directed from
pred1->target() to pred2->target().
| Precondition: | The interior of c is disjoint from all existing arrangement
vertices and edges.
|
| Precondition: | pred1->target() and pred2->target() are associated
with c's endpoints.
|
| Precondition: | If pred1->target and pred2->target() are already
connected by an edge, this edge represents an -monotone
curve that is interior-disjoint from c). |
|
|
|
advanced
|
|
Modifying Vertices and Edges:
|
Vertex_handle
|
arr.modify_vertex ( Vertex_handle v, Point_2 p)
|
| |
sets p to be the point associated with the vertex v.
The function returns a handle for the modified vertex (same as v).
| Precondition: | v is not a vertex at infinity and p is
geometrically equivalent to the point currently associated
with v. |
|
|
|
Face_handle
|
arr.remove_isolated_vertex ( Vertex_handle v)
|
| |
removes the isolated vertex v from the arrangement. The function
returns the face f that used to contain the isolated vertex.
| Precondition: | v is an isolated vertex (has no incident edges). |
|
|
|
Halfedge_handle
|
arr.modify_edge ( Halfedge_handle e, X_monotone_curve_2 c)
|
| |
sets c to be the -monotone curve associated with the edge e.
The function returns a handle for the modified edge (same as e).
| Precondition: | c is geometrically equivalent to the curve currently
associated with e. |
|
|
|
Halfedge_handle
|
arr.split_edge ( Halfedge_handle e, X_monotone_curve_2 c1, X_monotone_curve_2 c2)
|
| |
splits the edge e into two edges (more precisely, into two halfedge
pairs), associated with the given subcurves c1 and c2, and
creates a vertex that corresponds to the split point.
The function returns a handle for the halfedge, whose source is the same
as e->source() and whose target vertex is the split point.
| Precondition: | Either c1's left endpoint and c2's right endpoint
correspond to e's end-vertices such that c1's right endpoint
and c2's left endpoint are equal and define the split point -
or vice-versa (with change of roles between c1 and c2). |
|
|
|
Halfedge_handle
|
arr.merge_edge ( Halfedge_handle e1, Halfedge_handle e2, X_monotone_curve_2 c)
|
| |
merges the edges represented by e1 and e2 into
a single edge, associated with the given merged curve c.
Denote e1's end-vertices as and , while e2's
end-vertices are denoted and . The function removes the
common vertex returns a handle for one of the merged halfedges,
directed from to .
| Precondition: | e1 and e2 share a common end-vertex, such that the
two other end-vertices of the two edges are associated with c's
endpoints. |
|
|
|
Face_handle
|
arr.remove_edge ( Halfedge_handle e, bool remove_source = true, bool remove_target = true)
|
| |
removes the edge e from the arrangement. Since the e may
be the only edge incident to its source vertex (or its target vertex),
this vertex can be removed as well. The flags remove_source and
remove_target indicate whether the endpoints of e should be
removed, or whether they should be left as isolated vertices in the
arrangement.
If the operation causes two faces to merge, the merged face is returned.
Otherwise, the face to which the edge was incident is returned.
|
Miscellaneous
|
bool
|
arr.is_valid ()
|
returns true if arr represents a valid instance of
Arrangement_2<Traits,Dcel>. In particular, the functions checks the topological
structure of the arrangement and assures that it is valid. In addition,
the function performs several simple geometric tests to ensure the
validity of some of the geometric properties of the arrangement. Namely,
it checks that all arrangement vertices are associated with distinct
points, and that the halfedges around every vertex are ordered clockwise.
|
See Also
ArrangementDcel
Arr_default_dcel<Traits>
ArrangementBasicTraits_2
CGAL::is_valid
Insertion functions
(CGAL::insert_curve,
CGAL::insert_x_monotone_curve,
CGAL::insert_x_monotone_curves,
CGAL::insert_non_intersecting_curve,
CGAL::insert_non_intersecting_curves,
CGAL::insert_point)
Removal functions
(CGAL::remove_edge,
CGAL::remove_vertex)
CGAL::overlay
Input/output functions
(CGAL::read,
CGAL::write)
