2D Arrangement (Arrangement_2)

Definition

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::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.
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. Both 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
	Point;
typedef typename Traits::X_curve
	X_curve;
typedef typename Traits::Curve
	Curve;

Creation

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

Operations

Curve_iterator	arr.insert ( Curve cv)
		insert the curve cv into the arrangement. It uses the Traits::make_x_monotone function to cut the curve into $$x-monotone curves and inserts them in the hierarchy tree. If the arrangement is in update mode (the default mode) then the curves are inserted into the planar map.

template <class F_iterator>
Curve_iterator	arr.insert ( Curve 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& c, list<Curve>& l);

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_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)
Halfedge_handle	arr.locate ( Point p, Locate_type& lt)
Halfedge_handle	arr.vertical_ray_shoot ( Point p, Locate_type& lt, bool up)
Face_handle	arr.unbounded_face ()

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.