CGAL 5.6 - 2D Arrangements
Loading...
Searching...
No Matches
CGAL::Arrangement_with_history_2< Traits, Dcel > Class Template Reference

#include <CGAL/Arrangement_with_history_2.h>

Inherits from

CGAL::Arrangement_on_surface_with_history_2< Traits, Default_planar_topology< Traits, Dcel >::Traits >.

Definition

template<typename Traits, typename Dcel>
class CGAL::Arrangement_with_history_2< Traits, Dcel >

An object arr of the class Arrangement_with_history_2 represents the planar subdivision induced by a set of input curves \( \cal C\). The arrangement is represented as a doubly-connected edge-list (DCEL). As is the case for the Arrangement_2<Traits,Dcel>, each DCEL vertex is associated with a point and each edge is associated with an \( x\)-monotone curve whose interior is disjoint from all other curves and points. Each such \( x\)-monotone curve is a subcurve of some \( C \in \cal C\), or may represent an overlap among several curves in \( \cal C\).

The Arrangement_with_history_2 class-template extends the Arrangement_2 class-template by keeping an additional container of input curves representing \( \cal C\), and by maintaining a cross-mapping between these curves and the arrangement edges they induce. This way it is possible to determine the inducing curve(s) of each arrangement edge. This mapping also allows the traversal of input curves, and the traversal of edges induced by each curve.

The Arrangement_with_history_2 template has two parameters:

  • The Traits template-parameter should be instantiated with a model of the ArrangementTraits_2 concept. The traits class defines the Curve_2 type, which represents an input curve. It also defines the types of \( x\)-monotone curves and two-dimensional points, namely ArrangementTraits_2::X_monotone_curve_2 and ArrangementTraits_2::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 ArrangementDcelWithRebind concept. The value of this parameter is by default Arr_default_dcel<Traits>.
See also
ArrangementDcel
Arr_default_dcel<Traits>
ArrangementTraits_2
Arrangement_2<Traits,Dcel>
insertion functions
removal functions
overlaying arrangements
Examples
Arrangement_on_surface_2/curve_history.cpp, Arrangement_on_surface_2/edge_manipulation_curve_history.cpp, and Arrangement_on_surface_2/io_curve_history.cpp.

Types

typedef Traits Geometry_traits
 the geometry traits class.
 
typedef Default_planar_topology< Geometry_traits, Dcel >::Traits Topology_traits
 The topology traits.
 
typedef Arrangement_on_surface_with_history_2< Geometry_traits, Topology_traitsBase
 The base arrangement on surface type.
 

Types inherited from the base Arrangement_on_surface_2_with_history_2.

typedef Base::Point_2 Point_2
 
typedef Base::X_monotone_curve_2 X_monotone_curve_2
 
typedef Base::Curve_2 Curve_2
 
typedef Base::Size Size
 
typedef Base::Curve_handle Curve_handle
 
typedef Base::Curve_iterator Curve_iterator
 
typedef Base::Induced_edge_iterator Induced_edge_iterator
 
typedef Base::Originating_curve_iterator Originating_curve_iterator
 

Creation

 Arrangement_with_history_2 ()
 constructs an empty arrangement containing one unbounded face, which corresponds to the whole plane.
 
 Arrangement_with_history_2 (const Arrangement_with_history_2< Traits, Dcel > &other)
 copy constructor.
 
 Arrangement_with_history_2 (const Traits *traits)
 constructs an empty arrangement that uses the given traits instance for performing the geometric predicates.
 

Assignment Methods

Arrangement_with_history_2< Traits, Dcel > & operator= (other)
 assignment operator.
 
void assign (const Arrangement_with_history_2< Traits, Dcel > &other)
 assigns the contents of another arrangement.
 
void clear ()
 clears the arrangement.
 

Access Functions

Traits * traits ()
 obtains the traits object used by the arrangement instance.
 

Additional Inherited Members

- Public Types inherited from CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >
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_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.
 
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).
 
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.
 
- Public Member Functions inherited from CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >
 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.
 
Selfoperator= (other)
 assignment operator.
 
void assign (const Self &other)
 assigns the contents of another arrangement.
 
void clear ()
 clears the arrangement.
 
Geometry_traits_2geometry_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).
 
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.
 
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.
 
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.
 
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.
 
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().
 
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.
 
bool is_valid () const
 obtains true if arr represents a valid instance of Arrangement_on_surface_2.
 

Member Function Documentation

◆ traits()

template<typename Traits , typename Dcel >
Traits * CGAL::Arrangement_with_history_2< Traits, Dcel >::traits ( )

obtains the traits object used by the arrangement instance.

A const version is also available.