2D Arrangements

The arrangement class holds a planar map and a hierarchy tree. Vertices, halfedges and faces of the arrangement are derived from those of the planar map (with the additional functionality of the arrangement), in the same way that the vertices, halfedges and faces of the topological map class are derived from those of the Dcel class (see Chapter).

The hierarchy tree is implemented using the *In_place_list*
class (see the chapter on STL Extensions in the Support Library Manual).
Every level of a curve
hierarchy is a list of tree nodes.The *Curve_node* and
*Edge_node* of
the hierarchy derive from *Subcurve_node*. This enables the
polymorphic structure of the tree. The *Subcurve_node* is
derived from the *Base_node* which is a template parameter
of the arrangement. This enables the addition of attributes to the nodes
of the hierarchy tree by adding them inside the *Base_node*.

As part of the *Dcel* we define requirements for its vertex, halfedge and
face constituents. If we consider these constituents as (informally)
subconcepts of the *Dcel* concept then we have the following models for
its constituents.

The *Arr_2_vertex_base<Point>* is a model for the
Dcel vertex subconcept,
the *Arr_2_halfedge_base<Base_node>* is a
model for the Dcel halfedge subconcept
and the *Arr_2_face_base* is a
model for the Dcel face subconcept.

*#include <CGAL/Arr_2_bases.h>*

The *Arr_2_default_dcel<Traits>* is a model of the Dcel concept
described above. Its template parameter is the traits class.
It is a wrapper for *Pm_dcel* instantiated
with *Arr_2_vertex_base<Traits::Point>*,

*Arr_2_halfedge_base<Arr_base_node<Traits::X_curve> >* and
*Arr_2_face_base*.

*#include <CGAL/Arr_2_default_dcel.h>*

- Line segments. We actually have two traits classes for line segments:
*Arr_segment_traits_2*that heavily relies on the CGAL kernel and*Arr_segment_cached_traits_2*, which stores extra chached information regarding the segments to achieve faster running times. - Polylines, which are piecewise linear curves (a sequence of line segments
where each to neighboring segments share a common endpoint). The
*Arr_polyline_traits_2*class is used to construct arrangements of polylines. - Conic arcs, or bounded segments of algenraic curves of degree 2 at most
(such as circles, hyperbolic arcs and line segments). The
*Arr_conic_traits_2*supports this family of curves.

Since the requirements of the arrangement traits are a superset of the requirements of the Planar Map Traits and Planer Map with Intersection Traits, any traits class that works with arrangements can work with planar maps as well.

Next chapter: 2D Sweep Line of Planar Curves

The CGAL Project .
Tue, December 21, 2004 .