Navigation: Up, Table of Contents, Bibliography, Index, Title Page

## CGAL::Arrangement_2<Dcel,Traits,Base_node>

### Definition

An object arr of the class Arrangement_2<Dcel,Traits,Base_node> represents the planar subdivision induced by a set of curves that are not necessarily x-monotone and possibly intersecting. This class extends the class Planar_map_2<Dcel,Traits> which handles x-monotone pairwise interior disjoint curves.

This class also provides additional methods to traverse the resulting planar-map along curves inserted into the arrangement (note that a single curve in the arrangement might correspond to several edges of the planar map).

#include <CGAL/Arrangement_2.h>

The base class of Halfedge has additional properties apart from the ones defined for planar maps.

### Types

Arrangement_2<Dcel,Traits,Base_node>::Curve_node
| represents a curve inserted into the arrangement, which possibly intersects other curves in the arrangement, and is not necessarily x-monotone.
Arrangement_2<Dcel,Traits,Base_node>::Subcurve_node
| represents a subcurve of the curve inserted into the arrangement. It is created by invoking a user defined split_function on the original curve, or on another curve. By default a subcurve is created from the original curve by invoking the function Traits::curve_make_x_monotone().
Arrangement_2<Dcel,Traits,Base_node>::Edge_node
| represents a subcurve of the curve inserted into the arrangement which is created by an intersection with another curve. It holds a curve which is disjoint in its interior from the other curves in the arrangement, and holds a cross reference to the Halfedge in the planar map representing it.
Arrangement_2<Dcel,Traits,Base_node>::Vertex
| represents a vertex of the planar map induced by the arrangement.
Arrangement_2<Dcel,Traits,Base_node>::Halfedge
| represents a halfedge of the planar map induced by the arrangement. It has additional methods, see class definition of Arrangement_2<Dcel,Traits,Base_node>::Halfedge .
Arrangement_2<Dcel,Traits,Base_node>::Face
| represents a face of the planar map induced by the arrangement.

The following handles, iterators and circulators have appropriate constant counterparts. The mutable types are assignable to their constant counterparts. All circulators are assignable to the Halfedge_iterator. The iterators are assignable to the respective handle types. Wherever the handles appear in function parameter lists, the appropriate iterator can be used as well.

Arrangement_2<Dcel,Traits,Base_node>::Curve_iterator
| A bidirectional iterator over all Curve nodes of the arrangement. Its value-type is Curve_node.
Arrangement_2<Dcel,Traits,Base_node>::Subcurve_iterator
| a bidirectional iterator over all the subcurves which were created from the same original curve. Its value-type is Subcurve_node.
Arrangement_2<Dcel,Traits,Base_node>::Edge_iterator
| a bidirectional iterator over all the Edge_nodes which were created from the same original curve. Its value-type is Edge_node.
Arrangement_2<Dcel,Traits,Base_node>::Vertex_handle
| handle to vertex.
Arrangement_2<Dcel,Traits,Base_node>::Halfedge_handle
| handle to halfedge.
Arrangement_2<Dcel,Traits,Base_node>::Face_iterator
| handle to face
Arrangement_2<Dcel,Traits,Base_node>::Vertex_iterator
| a bidirectional iterator over the vertices of the arrangement. Its value-type is Vertex.
Arrangement_2<Dcel,Traits,Base_node>::Halfedge_iterator
| a bidirectional iterator over the halfedges of the arrangement. Its value-type is Halfedge.
Arrangement_2<Dcel,Traits,Base_node>::Face_iterator
| a bidirectional iterator over the faces of the arrangement. Its value-type is Face.
Arrangement_2<Dcel,Traits,Base_node>::Ccb_halfedge_circulator
| a forward circulator over the edges of a CCB (connected components of the boundary). Its value-type is Halfedge.
Arrangement_2<Dcel,Traits,Base_node>::Halfedge_around_vertex_circulator
| a forward circulator over the half-edges which have the vertex as their source. The half-edges are traversed in their clockwise order around the vertex. Its value-type is Halfedge.
Arrangement_2<Dcel,Traits,Base_node>::Holes_iterator
| a bidirectional iterator to traverse all the holes (i.e., inner CCBs) of a face (Holes_iterator++ is the next hole in the face). Its value type is Ccb_halfedge_circulator.
Arrangement_2<Dcel,Traits,Base_node>::Overlap_circulator
| a bidirectional circulator over the overlapping edge nodes that correspond to a single pair of halfedges. Its value-type is Edge_node and it can be cast to an Edge_iterator.

typedef Planar_map_2<Dcel,Traits>
| Planar_map; | the planar map type of the arrangement.

Arrangement_2<Dcel,Traits,Base_node>::Locate_type
| same as the planar map locate type.

typedef typename Traits::Point_2
| Point_2; | the point type of the arrangement
typedef typename Traits::Curve_2
| Curve_2; | the curve type of the arrangement. Objects of this type are inserted to the arrangement.
typedef typename Traits::X_monotone_curve_2
| X_monotone_curve_2; | the x-monotone curve type of the arrangement. The input curves of type Curve_2 are divided into x-monotone subcurves.

### Creation

Arrangement_2<Dcel,Traits,Base_node> arr;
| create an empty arrangement with the default point location strategy.
Arrangement_2<Dcel,Traits,Base_node> arr ( | Pm_point_location_base<Planar_map> *pl);
| create an empty arrangement with *pl as the point location strategy.
Arrangement_2<Dcel,Traits,Base_node> arr ( | Traits tr, Pm_point_location_base<Planar_map> *pl);
| create an empty arrangement with tr as the traits class and *pl as the point location strategy.

### Operations

void | arr.clear () | clears the arrangement.
Curve_iterator | arr.insert ( Curve_2 cv)
|  | inserts the curve cv into the arrangement. It uses the Traits::curve_make_x_monotone function to cut the curve into x-monotone subcurves and inserts them to the hierarchy tree. If the arrangement is in update mode (the default mode) then the curves are inserted into the planar map. Precondition: cv is not equivalent to a point.

template <class InputIterator>

void | arr.insert ( InputIterator begin, InputIterator end)
|  | insert the curves from a container iterated by InputIterator from begin to end into the arrangement. This function uses the sweep-line algorithm to perform the aggregated insertion.

| advanced |

template <class F_iterator>
Curve_iterator |
arr.insert ( | Curve_2 cv, F_iterator F_begin, F_iterator F_end)
|  | insert the curve cv into the arrangement. F_begin and F_end are iterators that refer to split-function pointers (or pointers to split-function objects). The insert function uses the split-functions to cut the curve into subcurves and inserts them in the hierarchy tree (every split-function creates one level of the hierarchy tree). If the arrangement is in update mode (the default mode) then the curves are inserted into the planar map.

The split-function should get as input a curve and a reference to a list of curves (where the subcurves will be stored), its return value is void. See Section and Section for examples of user-defined functions. The functions are called with the following syntax:

(*(*F_begin))(const Curve_2& c, list<Curve_2>& l);

| advanced |

| advanced |

### Reading Arrangement

bool | arr.read ( istream &in)
|  | reading Arrangement_2<Dcel,Traits,Base_node> from a given input stream. The input stream should support the extractor operator (>>) for the Point_2 and Curve_2 types of Arrangement.

template <class Scanner>

bool | arr.read ( istream &in, Scanner& scanner)
|  | reading Arrangement_2<Dcel,Traits,Base_node> from a given input stream when taking the scanner class as a parameter. The input stream should support the extractor operator (>>) for the Point_2 and Curve_2 types of Arrangement.

| advanced |

void | arr.set_update ( bool u)
|  | sets update mode to u. If update mode is true then every curve inserted into the arrangement is also inserted into the planar map induced by it (i.e., it is intersected with the rest of the curves in the arrangement). If update mode is false then the curve is only split into x-monotone curves and inserted into the hierarchy tree (without the edge level which is not constructed). If update mode is changed from false to true then the planar map is updated with all the curves inserted into the arrangement since the last time update was true.
Curve_iterator | arr.curve_node_begin ()
|  | returns the begin iterator of the curves (i.e., the curves that were inserted to arr).
Curve_iterator | arr.curve_node_end ()
|  | returns the past-the-end iterator of the curves.
void | arr.remove_curve ( Curve_iterator cit)
|  | removes the curve and all it's subcurves from the arrangement.

The following operations have the same functionality as their counterparts in the planar map.

Vertex_iterator | arr.vertices_begin ()
Vertex_iterator | arr.vertices_end ()
Size | arr.number_of_vertices ()
Halfedge_iterator | arr.halfedges_begin ()
Halfedge_iterator | arr.halfedges_end ()
Size | arr.number_of_halfedges ()
Face_iterator | arr.faces_begin ()
Face_iterator | arr.faces_end ()
Size | arr.number_of_faces ()
Halfedge_handle |
arr.split_edge ( | Halfedge_handle e, X_monotone_curve_2 c1, X_monotone_curve_2 c2)
Halfedge_handle | arr.locate ( Point_2 p, Locate_type& lt)
Halfedge_handle |
arr.vertical_ray_shoot ( | Point_2 p, Locate_type& lt, bool up)
Face_handle | arr.unbounded_face ()
bool | arr.is_valid ( bool verbose=false)
|  | checks the validity of many features of the arrangements. First, checks the validity of the arrangement's planar map. Then, checks for the correctness of the hierarchy tree. Finally, some geometric properties are verified, e.g., each edge's end point is the start point of its next edge. if the verboseparameter is true then a verbose description of the validity check is sent to the output.

The planar map operations: merge_edge and remove_edge are not implemented in the arrangement level, since they can cause inconsistencies between the hierarchy tree and the planar map. If it is necessary for the users to perform these operations they can still achieve this. For example, if the users need to remove an edge they can remove the curve and insert the two subcurves that are created after the edge is removed, instead of the original curve.

Next: ArrangementBaseNode_2

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .