Definition

template<typename GeometryTraits, typename TopologyTraits>
class CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >

An object aos of the class Arrangement_on_surface_2 represents the 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_on_surface_2 template has two parameters:

The GeometryTraits template-parameter should be instantiated with a model of a geometry traits. The minimal requirements are defined by the ArrangementBasicTraits_2 concept. A model of this concept defines the types of \( x\)-monotone curves and two-dimensional points, namely ArrangementBasicTraits_2::X_monotone_curve_2 and ArrangementBasicTraits_2::Point_2, respectively, and supports basic geometric predicates on them.
The TopologyTraits template-parameter should be instantiated with a class that is a model of the ArrangementTopologyTraits concept.

The available traits classes and Dcel classes are described below.

See also: ArrangementDcel; Arr_default_dcel<Traits>; ArrangementBasicTraits_2; CGAL::overlay(); CGAL::is_valid()

Insertion Functions

See also: CGAL::insert(); CGAL::insert_non_intersecting_curve(); CGAL::insert_non_intersecting_curves(); CGAL::insert_point()

Removal functions

See also: CGAL::remove_edge(); CGAL::remove_vertex()

Input/output functions

See also: CGAL::IO::read(); CGAL::IO::write()

Drawing function

See also: Drawing

Examples: Arrangement_on_surface_2/spherical_insert.cpp.

Classes
class	Face
	An object of the class `Face` represents an arrangement face, namely, a \(2\)-dimensional arrangement cell. More...

class	Halfedge
	An object \( e\) of the class `Halfedge` represents a halfedge in the arrangement. More...

class	Vertex
	An object \( v\) of the class `Vertex` represents an arrangement vertex, that is a \( 0\)-dimensional cell, associated with a point on the ambient surface. More...

Types
typedef GeometryTraits	Geometry_traits_2
	the geometry traits class in use.

typedef TopologyTraits	Topology_traits
	the topology traits class in use.

typedef Arrangement_on_surface_2< Geometry_traits_2, Topology_traits >	Self
	a private type used as an abbreviation of the `Arrangement_on_surface_2` type hereafter.

typedef Geometry_traits_2::Point_2	Point_2
	the point type, as defined by the traits class.

typedef Geometry_traits_2::X_monotone_curve_2	X_monotone_curve_2
	the \( x\)-monotone curve type, as defined by the traits class.

typedef Dcel::Size	Size
	the size type (equivalent to `size_t`).

The following mutable handles, iterators, and circulators have respective constant counterparts. 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. All handles are model of `LessThanComparable` and `Hashable`, that is they can be used as keys in containers such as `std::map` and `boost::unordered_map`.
typedef unspecified_type	Vertex_handle
	Mutable.

typedef unspecified_type	Halfedge_handle
	a handle to a halfedge.

typedef unspecified_type	Face_handle
	a handle to an arrangement face.

typedef unspecified_type	Vertex_iterator
	a bidirectional iterator over the vertices of the arrangement.

typedef unspecified_type	Halfedge_iterator
	a bidirectional iterator over the halfedges of the arrangement.

typedef unspecified_type	Edge_iterator
	a bidirectional iterator over the edges of the arrangement.

typedef unspecified_type	Face_iterator
	a bidirectional iterator over the faces of arrangement.

typedef unspecified_type	Unbounded_face_iterator
	a bidirectional iterator over the unbounded faces of arrangement.

typedef unspecified_type	Halfedge_around_vertex_circulator
	a bidirectional circulator over the halfedges that have a given vertex as their target.

typedef unspecified_type	Ccb_halfedge_circulator
	a bidirectional circulator over the halfedges of a CCB (connected component of the boundary).

typedef unspecified_type	Inner_ccb_iterator
	a bidirectional iterator over the inner CCBs of a given face.

typedef unspecified_type	Outer_ccb_iterator
	a bidirectional iterator over the outer CCBs of a given face.

typedef unspecified_type	Hole_iterator
	a bidirectional iterator over the holes (i.e., inner CCBs) contained inside a given face.

typedef unspecified_type	Isolated_vertex_iterator
	a bidirectional iterator over the isolated vertices contained inside a given face.

typedef unspecified_type	Vertex_const_handle
	Constant.

typedef unspecified_type	Halfedge_const_handle
	a handle to a halfedge.

typedef unspecified_type	Face_const_handle
	a handle to an arrangement face.

typedef unspecified_type	Vertex_const_iterator
	a bidirectional iterator over the vertices of the arrangement.

typedef unspecified_type	Halfedge_const_iterator
	a bidirectional iterator over the halfedges of the arrangement.

typedef unspecified_type	Edge_const_iterator
	a bidirectional iterator over the edges of the arrangement.

typedef unspecified_type	Face_const_iterator
	a bidirectional iterator over the faces of arrangement.

typedef unspecified_type	Unbounded_face_const_iterator
	a bidirectional iterator over the unbounded faces of arrangement.

typedef unspecified_type	Halfedge_around_vertex_const_circulator
	a bidirectional circulator over the halfedges that have a given vertex as their target.

typedef unspecified_type	Ccb_halfedge_const_circulator
	a bidirectional circulator over the halfedges of a CCB (connected component of the boundary).

typedef unspecified_type	Inner_ccb_const_iterator
	a bidirectional iterator over the inner CCBs of a given face.

typedef unspecified_type	Outer_ccb_const_iterator
	a bidirectional iterator over the outer CCBs of a given face.

typedef unspecified_type	Hole_const_iterator
	a bidirectional iterator over the holes (i.e., inner CCBs) contained inside a given face.

typedef unspecified_type	Isolated_vertex_const_iterator
	a bidirectional iterator over the isolated vertices contained inside a given face.

Creation
	Arrangement_on_surface_2 ()
	constructs an empty arrangement containing one unbounded face, which corresponds to the entire plane.

	Arrangement_on_surface_2 (const Self &other)
	copy constructor.

	Arrangement_on_surface_2 (const GeometryTraits *traits)
	constructs an empty arrangement that uses the given `traits` instance for performing the geometric predicates.

Assignment Methods
Self &	operator= (other)
	assignment operator.

void	assign (const Self &other)
	assigns the contents of another arrangement.

void	clear ()
	clears the arrangement.

Access Functions
Geometry_traits_2 *	geometry_traits ()
	obtains the traits object used by the arrangement instance.

bool	is_empty () const
	determines whether the arrangement is empty (contains only the unbounded face, with no vertices or edges).

Accessing the Arrangement Vertices
All `_begin()` and `_end()` methods listed below also have `const` counterparts, returning constant iterators instead of mutable ones.
Size	number_of_vertices () const
	obtains the number of vertices in the arrangement.

Size	number_of_isolated_vertices () const
	obtains the total number of isolated vertices in the arrangement.

Vertex_iterator	vertices_begin ()
	obtains the begin-iterator of the vertices in the arrangement.

Vertex_iterator	vertices_end ()
	obtains the past-the-end iterator of the vertices in the arrangement.

Iterator_range< Prevent_deref< Vertex_iterator > >	vertex_handles ()
	obtains a range over handles of the arrangement vertices.

Size	number_of_vertices_at_infinity () const
	obtains the number of arrangement vertices that lie at infinity and are not associated with valid points.

Accessing the Arrangement Halfedges
All `_begin()` and `_end()` methods listed below also have `const` counterparts, returning constant iterators instead of mutable ones.
Size	number_of_halfedges () const
	obtains the number of halfedges in the arrangement.

Halfedge_iterator	halfedges_begin ()
	obtains the begin-iterator of the halfedges in the arrangement.

Halfedge_iterator	halfedges_end ()
	obtains the past-the-end iterator of the halfedges in the arrangement.

Iterator_range< Prevent_deref< Halfedge_iterator > >	halfedge_handles ()
	obtains a range over handles of the arrangement halfedges.

Size	number_of_edges () const
	obtains the number of edges in the arrangement (equivalent to `arr.number_of_halfedges() / 2`).

Edge_iterator	edges_begin ()
	obtains the begin-iterator of the edges in the arrangement.

Edge_iterator	edges_end ()
	obtains the past-the-end iterator of the edges in the arrangement.

Iterator_range< Prevent_deref< Edge_iterator > >	edge_handles ()
	obtains a range over handles of the arrangement edges.

Accessing the Arrangement Faces
All `_begin()` and `_end()` methods listed below also have `const` counterparts, returning constant iterators instead of mutable ones.
Face_handle	unbounded_face ()
	obtains a handle for an unbounded face of the arrangement.

Size	number_of_faces () const
	obtains the number of faces in the arrangement.

Face_iterator	faces_begin ()
	obtains the begin-iterator of the faces in the arrangement.

Face_iterator	faces_end ()
	obtains the past-the-end iterator of the faces in the arrangement.

Iterator_range< Prevent_deref< Face_iterator > >	face_handles ()
	obtains a range over handles of the arrangement faces.

Size	number_of_unbounded_faces () const
	obtains the number of unbounded faces in the arrangement.

Unbounded_face_iterator	unbounded_faces_begin ()
	obtains the begin-iterator of the unbounded faces in the arrangement.

Unbounded_face_iterator	unbounded_faces_end ()
	obtains the past-the-end iterator of the unbounded faces in the arrangement.

Face_handle	fictitious_face ()
	obtains a handle to the fictitious face of the arrangement.

Casting Away Constness
It is sometimes 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 an 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	non_const_handle (Vertex_const_handle v)
	casts the given constant vertex handle to an equivalent mutable handle.

Halfedge_handle	non_const_handle (Halfedge_const_handle e)
	casts the given constant halfedge handle to an equivalent mutable handle.

Face_handle	non_const_handle (Face_const_handle f)
	casts the given constant face handle to an equivalent mutable handle.

Specialized Insertion Methods
Vertex_handle	insert_in_face_interior (const 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.

Halfedge_handle	insert_in_face_interior (const X_monotone_curve_2 &c, Face_handle f)
	inserts the curve `c` that is entirely contained in the interior of a given face `f`.

Halfedge_handle	insert_from_left_vertex (const 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.

Halfedge_handle	insert_from_right_vertex (const 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.

Halfedge_handle	insert_at_vertices (const 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`.

Halfedge_handle	insert_in_face_interior (const 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.

Halfedge_handle	insert_from_left_vertex (const 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.

Halfedge_handle	insert_from_left_vertex (const 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.

Halfedge_handle	insert_from_right_vertex (const 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.

Halfedge_handle	insert_from_right_vertex (const 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.

Halfedge_handle	insert_at_vertices (const 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`.

Halfedge_handle	insert_at_vertices (const 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()`.

Modifying Vertices and Edges
Vertex_handle	modify_vertex (Vertex_handle v, const Point_2 &p)
	sets `p` to be the point associated with the vertex `v`.

Face_handle	remove_isolated_vertex (Vertex_handle v)
	removes the isolated vertex `v` from the arrangement.

Halfedge_handle	modify_edge (Halfedge_handle e, const X_monotone_curve_2 &c)
	sets `c` to be the \( x\)-monotone curve associated with the edge `e`.

Halfedge_handle	split_edge (Halfedge_handle e, const X_monotone_curve_2 &c1, const 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.

Halfedge_handle	merge_edge (Halfedge_handle e1, Halfedge_handle e2, const X_monotone_curve_2 &c)
	merges the edges represented by `e1` and `e2` into a single edge, associated with the given merged curve `c`.

Face_handle	remove_edge (Halfedge_handle e, bool remove_source=true, bool remove_target=true)
	removes the edge `e` from the arrangement.

Miscellaneous
bool	is_valid () const
	obtains `true` if `arr` represents a valid instance of `Arrangement_on_surface_2`.