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 $$x-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 $$x-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 $$x-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>.

Self is an abbreviation of the Arrangement_2<Traits,Dcel> type hereafter.

#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 Arrangement_2<Traits_2,Dcel>
	Self;
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 $$x-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 $$0-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 $$1-dimensional cell in the subdivision. A halfedge is always associated with an $$x-monotone curve.
Arrangement_2<Traits,Dcel>::Face
	represents a $$2-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>::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.

$$ 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 the unbounded face of the arrangement.
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.

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 ( Halfedge_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 as a new hole (inner component) of the face f. As a result, two new vertices that correspond to c's endpoints are created and connected with a newly created halfedge pair. 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).
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. 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. 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: v1 and v2 are associated with c's endpoints. Precondition: If v1 and v2 are already connected by an edge, this edge represents an $$x-monotone curve that is interior-disjoint from c).

advanced

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_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_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 $$x-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 $$x-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: 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 c)
		sets c to be the $$x-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 $$u1 and $$v, while e2's end-vertices are denoted $$u2 and $$v. The function removes the common vertex $$v returns a handle for one of the merged halfedges, directed from $$u1 to $$u2. 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