CGAL 5.6.1 - 2D Arrangements
CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits > Class Template Reference

#include <CGAL/Arrangement_on_surface_2.h>

Inherited by CGAL::Arrangement_on_surface_with_history_2< GeometryTraits, TopologyTraits >.

Definition

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 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. More...
 
typedef TopologyTraits Topology_traits
 the topology traits class in use. More...
 
typedef Arrangement_on_surface_2< Geometry_traits_2, Topology_traitsSelf
 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. More...
 
typedef Geometry_traits_2::X_monotone_curve_2 X_monotone_curve_2
 the \( x\)-monotone curve type, as defined by the traits class. More...
 
typedef Dcel::Size Size
 the size type (equivalent to size_t). More...
 

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. More...
 
typedef unspecified_type Halfedge_handle
 a handle to a halfedge. More...
 
typedef unspecified_type Face_handle
 a handle to an arrangement face. More...
 
typedef unspecified_type Vertex_iterator
 a bidirectional iterator over the vertices of the arrangement. More...
 
typedef unspecified_type Halfedge_iterator
 a bidirectional iterator over the halfedges of the arrangement. More...
 
typedef unspecified_type Edge_iterator
 a bidirectional iterator over the edges of the arrangement. More...
 
typedef unspecified_type Face_iterator
 a bidirectional iterator over the faces of arrangement. More...
 
typedef unspecified_type Unbounded_face_iterator
 a bidirectional iterator over the unbounded faces of arrangement. More...
 
typedef unspecified_type Halfedge_around_vertex_circulator
 a bidirectional circulator over the halfedges that have a given vertex as their target. More...
 
typedef unspecified_type Ccb_halfedge_circulator
 a bidirectional circulator over the halfedges of a CCB (connected component of the boundary). More...
 
typedef unspecified_type Inner_ccb_iterator
 a bidirectional iterator over the inner CCBs of a given face. More...
 
typedef unspecified_type Outer_ccb_iterator
 a bidirectional iterator over the outer CCBs of a given face. More...
 
typedef unspecified_type Hole_iterator
 a bidirectional iterator over the holes (i.e., inner CCBs) contained inside a given face. More...
 
typedef unspecified_type Isolated_vertex_iterator
 a bidirectional iterator over the isolated vertices contained inside a given face. More...
 
typedef unspecified_type Vertex_const_handle
 Constant. More...
 
typedef unspecified_type Halfedge_const_handle
 a handle to a halfedge. More...
 
typedef unspecified_type Face_const_handle
 a handle to an arrangement face. More...
 
typedef unspecified_type Vertex_const_iterator
 a bidirectional iterator over the vertices of the arrangement. More...
 
typedef unspecified_type Halfedge_const_iterator
 a bidirectional iterator over the halfedges of the arrangement. More...
 
typedef unspecified_type Edge_const_iterator
 a bidirectional iterator over the edges of the arrangement. More...
 
typedef unspecified_type Face_const_iterator
 a bidirectional iterator over the faces of arrangement. More...
 
typedef unspecified_type Unbounded_face_const_iterator
 a bidirectional iterator over the unbounded faces of arrangement. More...
 
typedef unspecified_type Halfedge_around_vertex_const_circulator
 a bidirectional circulator over the halfedges that have a given vertex as their target. More...
 
typedef unspecified_type Ccb_halfedge_const_circulator
 a bidirectional circulator over the halfedges of a CCB (connected component of the boundary). More...
 
typedef unspecified_type Inner_ccb_const_iterator
 a bidirectional iterator over the inner CCBs of a given face. More...
 
typedef unspecified_type Outer_ccb_const_iterator
 a bidirectional iterator over the outer CCBs of a given face. More...
 
typedef unspecified_type Hole_const_iterator
 a bidirectional iterator over the holes (i.e., inner CCBs) contained inside a given face. More...
 
typedef unspecified_type Isolated_vertex_const_iterator
 a bidirectional iterator over the isolated vertices contained inside a given face. More...
 

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. More...
 
 Arrangement_on_surface_2 (const GeometryTraits *traits)
 constructs an empty arrangement that uses the given traits instance for performing the geometric predicates.
 

Assignment Methods

Selfoperator= (other)
 assignment operator. More...
 
void assign (const Self &other)
 assigns the contents of another arrangement. More...
 
void clear ()
 clears the arrangement. More...
 

Access Functions

Geometry_traits_2geometry_traits ()
 obtains the traits object used by the arrangement instance. More...
 
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. More...
 
Size number_of_isolated_vertices () const
 obtains the total number of isolated vertices in the arrangement. More...
 
Vertex_iterator vertices_begin ()
 obtains the begin-iterator of the vertices in the arrangement. More...
 
Vertex_iterator vertices_end ()
 obtains the past-the-end iterator of the vertices in the arrangement. More...
 
Iterator_range< Prevent_deref< Vertex_iterator > > vertex_handles ()
 obtains a range over handles of the arrangement vertices. More...
 
Size number_of_vertices_at_infinity () const
 obtains the number of arrangement vertices that lie at infinity and are not associated with valid points. More...
 

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. More...
 
Halfedge_iterator halfedges_begin ()
 obtains the begin-iterator of the halfedges in the arrangement. More...
 
Halfedge_iterator halfedges_end ()
 obtains the past-the-end iterator of the halfedges in the arrangement. More...
 
Iterator_range< Prevent_deref< Halfedge_iterator > > halfedge_handles ()
 obtains a range over handles of the arrangement halfedges. More...
 
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. More...
 
Edge_iterator edges_end ()
 obtains the past-the-end iterator of the edges in the arrangement. More...
 
Iterator_range< Prevent_deref< Edge_iterator > > edge_handles ()
 obtains a range over handles of the arrangement edges. More...
 

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. More...
 
Size number_of_faces () const
 obtains the number of faces in the arrangement. More...
 
Face_iterator faces_begin ()
 obtains the begin-iterator of the faces in the arrangement. More...
 
Face_iterator faces_end ()
 obtains the past-the-end iterator of the faces in the arrangement. More...
 
Iterator_range< Prevent_deref< Face_iterator > > face_handles ()
 obtains a range over handles of the arrangement faces. More...
 
Size number_of_unbounded_faces () const
 obtains the number of unbounded faces in the arrangement. More...
 
Unbounded_face_iterator unbounded_faces_begin ()
 obtains the begin-iterator of the unbounded faces in the arrangement. More...
 
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. More...
 

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. More...
 
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. More...
 

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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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(). More...
 

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. More...
 
Face_handle remove_isolated_vertex (Vertex_handle v)
 removes the isolated vertex v from the arrangement. More...
 
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. More...
 
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. More...
 
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. More...
 
Face_handle remove_edge (Halfedge_handle e, bool remove_source=true, bool remove_target=true)
 removes the edge e from the arrangement. More...
 

Miscellaneous

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

Member Typedef Documentation

◆ Ccb_halfedge_circulator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

◆ Ccb_halfedge_const_circulator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Ccb_halfedge_const_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.

◆ Edge_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Edge_const_iterator

a bidirectional iterator over the edges of the arrangement.

(That is, it skips every other halfedge.) Its value-type is Halfedge.

◆ Edge_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Edge_iterator

a bidirectional iterator over the edges of the arrangement.

(That is, it skips every other halfedge.) Its value-type is Halfedge.

◆ Face_const_handle

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Face_const_handle

a handle to an arrangement face.

◆ Face_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Face_const_iterator

a bidirectional iterator over the faces of arrangement.

Its value-type is Face.

◆ Face_handle

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Face_handle

a handle to an arrangement face.

◆ Face_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Face_iterator

a bidirectional iterator over the faces of arrangement.

Its value-type is Face.

◆ Geometry_traits_2

template<typename GeometryTraits, typename TopologyTraits>
typedef GeometryTraits CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Geometry_traits_2

the geometry traits class in use.

◆ Halfedge_around_vertex_circulator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Halfedge_around_vertex_circulator

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

Its value-type is Halfedge.

◆ Halfedge_around_vertex_const_circulator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Halfedge_around_vertex_const_circulator

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

Its value-type is Halfedge.

◆ Halfedge_const_handle

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Halfedge_const_handle

a handle to a halfedge.

The halfedge and its twin form together an arrangement edge.

◆ Halfedge_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Halfedge_const_iterator

a bidirectional iterator over the halfedges of the arrangement.

Its value-type is Halfedge.

◆ Halfedge_handle

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Halfedge_handle

a handle to a halfedge.

The halfedge and its twin form together an arrangement edge.

◆ Halfedge_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Halfedge_iterator

a bidirectional iterator over the halfedges of the arrangement.

Its value-type is Halfedge.

◆ Hole_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Hole_const_iterator

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

Its value type is Ccb_halfedge_circulator.

◆ Hole_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Hole_iterator

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

Its value type is Ccb_halfedge_circulator.

◆ Inner_ccb_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Inner_ccb_const_iterator

a bidirectional iterator over the inner CCBs of a given face.

Its value type is Ccb_halfedge_circulator.

◆ Inner_ccb_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Inner_ccb_iterator

a bidirectional iterator over the inner CCBs of a given face.

Its value type is Ccb_halfedge_circulator.

◆ Isolated_vertex_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Isolated_vertex_const_iterator

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

Its value type is Vertex.

◆ Isolated_vertex_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Isolated_vertex_iterator

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

Its value type is Vertex.

◆ Outer_ccb_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Outer_ccb_const_iterator

a bidirectional iterator over the outer CCBs of a given face.

Its value type is Ccb_halfedge_circulator.

◆ Outer_ccb_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Outer_ccb_iterator

a bidirectional iterator over the outer CCBs of a given face.

Its value type is Ccb_halfedge_circulator.

◆ Point_2

template<typename GeometryTraits, typename TopologyTraits>
typedef Geometry_traits_2::Point_2 CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Point_2

the point type, as defined by the traits class.

◆ Size

template<typename GeometryTraits, typename TopologyTraits>
typedef Dcel::Size CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Size

the size type (equivalent to size_t).

◆ Topology_traits

template<typename GeometryTraits, typename TopologyTraits>
typedef TopologyTraits CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Topology_traits

the topology traits class in use.

◆ Unbounded_face_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Unbounded_face_const_iterator

a bidirectional iterator over the unbounded faces of arrangement.

Its value-type is Face.

◆ Unbounded_face_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Unbounded_face_iterator

a bidirectional iterator over the unbounded faces of arrangement.

Its value-type is Face.

◆ Vertex_const_handle

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Vertex_const_handle

Constant.

a handle to an arrangement vertex.

◆ Vertex_const_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Vertex_const_iterator

a bidirectional iterator over the vertices of the arrangement.

Its value-type is Vertex.

◆ Vertex_handle

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Vertex_handle

Mutable.

a handle to an arrangement vertex.

◆ Vertex_iterator

template<typename GeometryTraits, typename TopologyTraits>
typedef unspecified_type CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Vertex_iterator

a bidirectional iterator over the vertices of the arrangement.

Its value-type is Vertex.

◆ X_monotone_curve_2

template<typename GeometryTraits, typename TopologyTraits>
typedef Geometry_traits_2::X_monotone_curve_2 CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::X_monotone_curve_2

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

Constructor & Destructor Documentation

◆ Arrangement_on_surface_2()

template<typename GeometryTraits, typename TopologyTraits>
CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::Arrangement_on_surface_2 ( const Self other)

copy constructor.

Member Function Documentation

◆ assign()

template<typename GeometryTraits, typename TopologyTraits>
void CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::assign ( const Self other)

assigns the contents of another arrangement.

◆ clear()

template<typename GeometryTraits, typename TopologyTraits>
void CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::clear ( )

clears the arrangement.

◆ edge_handles()

template<typename GeometryTraits, typename TopologyTraits>
Iterator_range<Prevent_deref<Edge_iterator> > CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::edge_handles ( )

obtains a range over handles of the arrangement edges.

◆ edges_begin()

template<typename GeometryTraits, typename TopologyTraits>
Edge_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::edges_begin ( )

obtains the begin-iterator of the edges in the arrangement.

◆ edges_end()

template<typename GeometryTraits, typename TopologyTraits>
Edge_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::edges_end ( )

obtains the past-the-end iterator of the edges in the arrangement.

◆ face_handles()

template<typename GeometryTraits, typename TopologyTraits>
Iterator_range<Prevent_deref<Face_iterator> > CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::face_handles ( )

obtains a range over handles of the arrangement faces.

◆ faces_begin()

template<typename GeometryTraits, typename TopologyTraits>
Face_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::faces_begin ( )

obtains the begin-iterator of the faces in the arrangement.

◆ faces_end()

template<typename GeometryTraits, typename TopologyTraits>
Face_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::faces_end ( )

obtains the past-the-end iterator of the faces in the arrangement.

◆ fictitious_face()

template<typename GeometryTraits, typename TopologyTraits>
Face_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::fictitious_face ( )

obtains a handle to the fictitious face of the arrangement.

If the arrangement is not unbounded, there is no fictitious face. In this case the result is not deterministic. A const version is also available.

◆ geometry_traits()

template<typename GeometryTraits, typename TopologyTraits>
Geometry_traits_2* CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::geometry_traits ( )

obtains the traits object used by the arrangement instance.

A const version is also available.

◆ halfedge_handles()

template<typename GeometryTraits, typename TopologyTraits>
Iterator_range<Prevent_deref<Halfedge_iterator> > CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::halfedge_handles ( )

obtains a range over handles of the arrangement halfedges.

◆ halfedges_begin()

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::halfedges_begin ( )

obtains the begin-iterator of the halfedges in the arrangement.

◆ halfedges_end()

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::halfedges_end ( )

obtains the past-the-end iterator of the halfedges in the arrangement.

◆ insert_at_vertices() [1/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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.
c must not be an unbounded curve.
v1 and v2 are associated with c's endpoints.
If v1 and v2 are already connected by an edge, this edge represents an \( x\)-monotone curve that is interior-disjoint from c).

◆ insert_at_vertices() [2/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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.
pred1->target() and v2 are associated with c's endpoints.
If pred1->target and v2 are already connected by an edge, this edge represents an \( x\)-monotone curve that is interior-disjoint from c).

◆ insert_at_vertices() [3/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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().

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.
pred1->target() and pred2->target() are associated with c's endpoints.
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).

◆ insert_from_left_vertex() [1/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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.
v is associated with the left endpoint of c.
The right endpoint of c is not already associated with an existing arrangement vertex.

◆ insert_from_left_vertex() [2/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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.
pred->target() is associated with the left endpoint of c, and c should be inserted after pred in a clockwise order around this vertex.
The right endpoint of c is not already associated with an existing arrangement vertex.

◆ insert_from_left_vertex() [3/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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.
pred->target() is associated with the left endpoint of c, and c should be inserted after pred in a clockwise order around this vertex.
fict_pred is a fictitious halfedge that contains the unbounded right end of c.

◆ insert_from_right_vertex() [1/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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.
v is associated with the right endpoint of c.
The left endpoint of c is not already associated with an existing arrangement vertex.

◆ insert_from_right_vertex() [2/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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.
pred->target() is associated with the right endpoint of c, and c should be inserted after pred in a clockwise order around this vertex.
The left endpoint of c is not already associated with an existing arrangement vertex.

◆ insert_from_right_vertex() [3/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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.
pred->target() is associated with the right endpoint of c, and c should be inserted after pred in a clockwise order around this vertex.
fict_pred is a fictitious halfedge that contains the unbounded left end of c.

◆ insert_in_face_interior() [1/3]

template<typename GeometryTraits, typename TopologyTraits>
Vertex_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

Precondition
p lies in the interior of the face f.

◆ insert_in_face_interior() [2/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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).
In case c is an unbounded curve, f must be an unbounded face.

◆ insert_in_face_interior() [3/3]

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

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

◆ is_valid()

template<typename GeometryTraits, typename TopologyTraits>
bool CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::is_valid ( ) const

obtains true if arr represents a valid instance of Arrangement_on_surface_2.

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.

◆ merge_edge()

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

Denote e1's end-vertices as \( u_1\) and \( v\), while e2's end-vertices are denoted \( u_2\) and \( v\). The function removes the common vertex \( v\) returns a handle for one of the merged halfedges, directed from \( u_1\) to \( u_2\).

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.

◆ modify_edge()

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::modify_edge ( Halfedge_handle  e,
const X_monotone_curve_2 c 
)

sets c to be the \( x\)-monotone curve associated with the edge e.

The function obtains a handle for the modified edge (same as e).

Precondition
c is geometrically equivalent to the curve currently associated with e.

◆ modify_vertex()

template<typename GeometryTraits, typename TopologyTraits>
Vertex_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::modify_vertex ( Vertex_handle  v,
const 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.

◆ non_const_handle() [1/2]

template<typename GeometryTraits, typename TopologyTraits>
Vertex_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::non_const_handle ( Vertex_const_handle  v)

casts the given constant vertex handle to an equivalent mutable handle.

◆ non_const_handle() [2/2]

template<typename GeometryTraits, typename TopologyTraits>
Face_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::non_const_handle ( Face_const_handle  f)

casts the given constant face handle to an equivalent mutable handle.

◆ number_of_faces()

template<typename GeometryTraits, typename TopologyTraits>
Size CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::number_of_faces ( ) const

obtains the number of faces in the arrangement.

◆ number_of_halfedges()

template<typename GeometryTraits, typename TopologyTraits>
Size CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::number_of_halfedges ( ) const

obtains the number of halfedges in the arrangement.

◆ number_of_isolated_vertices()

template<typename GeometryTraits, typename TopologyTraits>
Size CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::number_of_isolated_vertices ( ) const

obtains the total number of isolated vertices in the arrangement.

◆ number_of_unbounded_faces()

template<typename GeometryTraits, typename TopologyTraits>
Size CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::number_of_unbounded_faces ( ) const

obtains the number of unbounded faces in the arrangement.

Note arr.number_of_faces() also counts the unbounded faces of the arrangement.

◆ number_of_vertices()

template<typename GeometryTraits, typename TopologyTraits>
Size CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::number_of_vertices ( ) const

obtains the number of vertices in the arrangement.

◆ number_of_vertices_at_infinity()

template<typename GeometryTraits, typename TopologyTraits>
Size CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::number_of_vertices_at_infinity ( ) const

obtains 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.

◆ operator=()

template<typename GeometryTraits, typename TopologyTraits>
Self& CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::operator= ( other  )

assignment operator.

◆ remove_edge()

template<typename GeometryTraits, typename TopologyTraits>
Face_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

◆ remove_isolated_vertex()

template<typename GeometryTraits, typename TopologyTraits>
Face_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::remove_isolated_vertex ( Vertex_handle  v)

removes the isolated vertex v from the arrangement.

The function obtains the face f that used to contain the isolated vertex.

Precondition
v is an isolated vertex (has no incident edges).

◆ split_edge()

template<typename GeometryTraits, typename TopologyTraits>
Halfedge_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::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.

The function obtains 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).

◆ unbounded_face()

template<typename GeometryTraits, typename TopologyTraits>
Face_handle CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::unbounded_face ( )

obtains 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.

◆ unbounded_faces_begin()

template<typename GeometryTraits, typename TopologyTraits>
Unbounded_face_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::unbounded_faces_begin ( )

obtains the begin-iterator of the unbounded faces in the arrangement.

◆ vertex_handles()

template<typename GeometryTraits, typename TopologyTraits>
Iterator_range<Prevent_deref<Vertex_iterator> > CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::vertex_handles ( )

obtains a range over handles of the arrangement vertices.

◆ vertices_begin()

template<typename GeometryTraits, typename TopologyTraits>
Vertex_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::vertices_begin ( )

obtains the begin-iterator of the vertices in the arrangement.

◆ vertices_end()

template<typename GeometryTraits, typename TopologyTraits>
Vertex_iterator CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >::vertices_end ( )

obtains the past-the-end iterator of the vertices in the arrangement.