CGAL 4.7 - 2D Arrangements: CGAL::Arrangement_2< Traits, Dcel > Class Template Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - 2D Arrangements

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Classes
CGAL::Arrangement_2< Traits, Dcel > Class Template Reference
2D Arrangement Reference

`#include <CGAL/Arrangement_2.h>`

Inherited by CGAL::Arrangement_with_history_2< Traits, Dcel >.

## Definition

An object `arr` of the class `Arrangement_2` represents the planar subdivision induced by a set of \( x\)-monotone curves and isolated points into maximally connected cells. The arrangement is represented as a doubly-connected edge-list (Dcel) such that each Dcel vertex is associated with a point of the plane and each edge is associated with an \( x\)-monotone curve whose interior is disjoint from all other edges and vertices. Recall that an arrangement edge is always comprised of a pair of twin Dcel halfedges.

The `Arrangement_2` template has two parameters:

- The `Traits` template-parameter should be instantiated with a model of the `ArrangementBasicTraits_2` concept. The traits class defines the types of \( x\)-monotone curves and two-dimensional points, namely `ArrangementBasicTraits_2::X_monotone_curve_2` and `ArrangementBasicTraits_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 `ArrangementDcel` concept. The value of this parameter is by default `Arr_default_dcel<Traits>`.

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::read()`
  `CGAL::write()`

Examples:
  Arrangement_on_surface_2/aggregated_insertion.cpp, Arrangement_on_surface_2/algebraic_curves.cpp, Arrangement_on_surface_2/algebraic_segments.cpp, Arrangement_on_surface_2/batched_point_location.cpp, Arrangement_on_surface_2/Bezier_curves.cpp, Arrangement_on_surface_2/bgl_dual_adapter.cpp, Arrangement_on_surface_2/bgl_primal_adapter.cpp, Arrangement_on_surface_2/circles.cpp, Arrangement_on_surface_2/circular_arcs.cpp, Arrangement_on_surface_2/conic_multiplicities.cpp, Arrangement_on_surface_2/conics.cpp, Arrangement_on_surface_2/consolidated_curve_data.cpp, Arrangement_on_surface_2/dcel_extension.cpp, Arrangement_on_surface_2/dcel_extension_io.cpp, Arrangement_on_surface_2/dual_lines.cpp, Arrangement_on_surface_2/dual_with_data.cpp, Arrangement_on_surface_2/edge_insertion.cpp, Arrangement_on_surface_2/edge_manipulation.cpp, Arrangement_on_surface_2/face_extension.cpp, Arrangement_on_surface_2/face_extension_overlay.cpp, Arrangement_on_surface_2/generic_curve_data.cpp, Arrangement_on_surface_2/global_insertion.cpp, Arrangement_on_surface_2/global_removal.cpp, Arrangement_on_surface_2/incremental_insertion.cpp, Arrangement_on_surface_2/io.cpp, Arrangement_on_surface_2/observer.cpp, Arrangement_on_surface_2/overlay.cpp, Arrangement_on_surface_2/overlay_unbounded.cpp, Arrangement_on_surface_2/point_location_example.cpp, Arrangement_on_surface_2/polylines.cpp, Arrangement_on_surface_2/predefined_kernel.cpp, Arrangement_on_surface_2/predefined_kernel_non_intersecting.cpp, Arrangement_on_surface_2/rational_functions.cpp, Arrangement_on_surface_2/unbounded_non_intersecting.cpp, Arrangement_on_surface_2/unbounded_rational_functions.cpp, and Arrangement_on_surface_2/vertical_ray_shooting.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 plane. More...

## Types

typedef Arrangement_2 < Traits_2, Dcel > | Self
| a private type used as an abbreviation of the `Arrangement_2` type hereafter.
typedef unspecified_type | Traits_2
| the traits class in use.
typedef Traits_2::Point_2 | Point_2
| the point type, as defined by the traits class.
typedef 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 handles, iterators, and circulators all have respective constant counterparts (for example, in addition to `Vertex_iterator` the type `Vertex_const_iterator` is also defined).

See [8] for a discussion of constant versus mutable iterator types. The mutable types are assignable to their constant counterparts. `Vertex_iterator`, `Halfedge_iterator`, and `Face_iterator` are equivalent to the respective handle types (namely, `Vertex_handle`, `Halfedge_handle`, and `Face_handle`). Thus, wherever the handles appear in function parameter lists, the respective iterators can be passed as well.

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
| a handle for an arrangement vertex.
typedef unspecified_type | Halfedge_handle
| a handle for a halfedge. More...
typedef unspecified_type | Face_handle
| a handle for an arrangement face.
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 | 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...

## Creation

| Arrangement_2 ()
| constructs an empty arrangement containing one unbounded face, which corresponds to the entire plane.
| Arrangement_2 (const Self &other)
| copy constructor.
| Arrangement_2 (const Traits_2 *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

Traits_2 * | get_traits ()
| returns 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
| returns the number of vertices in the arrangement.
Size | number_of_isolated_vertices () const
| returns the total number of isolated vertices in the arrangement.
Vertex_iterator | vertices_begin ()
| returns the begin-iterator of the vertices in the arrangement.
Vertex_iterator | vertices_end ()
| returns the past-the-end iterator of the vertices in the arrangement.
Size | number_of_vertices_at_infinity () const
| returns 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
| returns the number of halfedges in the arrangement.
Halfedge_iterator | halfedges_begin ()
| returns the begin-iterator of the halfedges in the arrangement.
Halfedge_iterator | halfedges_end ()
| returns the past-the-end iterator of the halfedges in the arrangement.
Size | number_of_edges () const
| returns the number of edges in the arrangement (equivalent to `arr.number_of_halfedges() / 2`).
Edge_iterator | edges_begin ()
| returns the begin-iterator of the edges in the arrangement.
Edge_iterator | edges_end ()
| returns the past-the-end iterator of the edges in the arrangement.

## 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 ()
| returns a handle for an unbounded face of the arrangement. More...
Size | number_of_faces () const
| returns the number of faces in the arrangement.
Face_iterator | faces_begin ()
| returns the begin-iterator of the faces in the arrangement.
Face_iterator | faces_end ()
| returns the past-the-end iterator of the faces in the arrangement.
Size | number_of_unbounded_faces () const
| returns the number of unbounded faces in the arrangement. More...
Unbounded_face_iterator | unbounded_faces_begin ()
| returns the begin-iterator of the unbounded faces in the arrangement.
Unbounded_face_iterator | unbounded_faces_end ()
| returns the past-the-end iterator of the unbounded faces in the arrangement.
Face_handle | fictitious_face ()
| returns 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.
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. 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
| returns `true` if `arr` represents a valid instance of `Arrangement_2`. More...

## Member Typedef Documentation

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Ccb_halfedge_circulator

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

Its value-type is `Halfedge`. Each bounded face has a single CCB representing it outer boundary, and may have several inner CCBs representing its holes.

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Edge_iterator

a bidirectional iterator over the edges of the arrangement.

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

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Face_iterator

a bidirectional iterator over the faces of arrangement.

Its value-type is `Face`.

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Halfedge_around_vertex_circulator

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

Its value-type is `Halfedge`.

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Halfedge_handle

a handle for a halfedge.

The halfedge and its twin form together an arrangement edge.

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Halfedge_iterator

a bidirectional iterator over the halfedges of the arrangement.

Its value-type is `Halfedge`.

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Hole_iterator

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

Its value type is `Ccb_halfedge_circulator`.

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Isolated_vertex_iterator

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

Its value type is `Vertex`.

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Unbounded_face_iterator

a bidirectional iterator over the unbounded faces of arrangement.

Its value-type is `Face`.

template<typename Traits , typename Dcel >

typedef unspecified_type CGAL::Arrangement_2< Traits, Dcel >::Vertex_iterator

a bidirectional iterator over the vertices of the arrangement.

Its value-type is `Vertex`.

## Member Function Documentation

template<typename Traits , typename Dcel >

Face_handle CGAL::Arrangement_2< Traits, Dcel >::fictitious_face | ( | ) |  |

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

template<typename Traits , typename Dcel >

Traits_2* CGAL::Arrangement_2< Traits, Dcel >::get_traits | ( | ) |  |

returns the traits object used by the arrangement instance.

A `const` version is also available.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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`).

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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`).

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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`).

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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`.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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`.

template<typename Traits , typename Dcel >

Vertex_handle CGAL::Arrangement_2< Traits, Dcel >::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`.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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.

template<typename Traits , typename Dcel >

bool CGAL::Arrangement_2< Traits, Dcel >::is_valid | ( | ) |  | const

returns `true` if `arr` represents a valid instance of `Arrangement_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.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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.

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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 returns a handle for the modified edge (same as `e`).

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

template<typename Traits , typename Dcel >

Vertex_handle CGAL::Arrangement_2< Traits, Dcel >::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`.

template<typename Traits , typename Dcel >

Size CGAL::Arrangement_2< Traits, Dcel >::number_of_unbounded_faces | ( | ) |  | const

returns the number of unbounded faces in the arrangement.

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

template<typename Traits , typename Dcel >

Size CGAL::Arrangement_2< Traits, Dcel >::number_of_vertices_at_infinity | ( | ) |  | const

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

template<typename Traits , typename Dcel >

Face_handle CGAL::Arrangement_2< Traits, Dcel >::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.

template<typename Traits , typename Dcel >

Face_handle CGAL::Arrangement_2< Traits, Dcel >::remove_isolated_vertex | ( | Vertex_handle | v) |  |

removes the isolated vertex `v` from the arrangement.

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

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

template<typename Traits , typename Dcel >

Halfedge_handle CGAL::Arrangement_2< Traits, Dcel >::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 returns a handle for the halfedge, whose source is the same as `e->source()` and whose target vertex is the split point.

Precondition
  Either `c1`'s left endpoint and `c2`'s right endpoint correspond to `e`'s end-vertices such that `c1`'s right endpoint and `c2`'s left endpoint are equal and define the split point - or vice-versa (with change of roles between `c1` and `c2`).

template<typename Traits , typename Dcel >

Face_handle CGAL::Arrangement_2< Traits, Dcel >::unbounded_face | ( | ) |  |

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