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 substituted by a model of a geometry traits. The minimal requirements are defined by the AosBasicTraits_2 concept. A model of this concept defines the types of \(x\)-monotone curves and two-dimensional points, namely AosBasicTraits_2::X_monotone_curve_2 and AosBasicTraits_2::Point_2, respectively, and supports basic geometric predicates on them.
The TopologyTraits template-parameter should be substituted by a class that is a model of the AosTopologyTraits concept.

The available traits classes and Dcel classes are described below.

See also: AosDcel; Arr_default_dcel<Traits>; AosBasicTraits_2; CGAL::overlay()

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/count_and_trace.cpp, and Arrangement_on_surface_2/polycurve_geodesic.cpp.

Classes
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...
class	Halfedge
	An object \(e\) of the class Halfedge represents a halfedge in the arrangement. More...
class	Face
	An object of the class Face represents an arrangement face, namely, a \(2\)-dimensional arrangement cell. 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 std::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.