Chapter 24
2D Arrangements

Ester Ezra, Eyal Flato, Dan Halperin, Iddo Hanniel, Shai Hirsch, and Ron Wein


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 Chapterreference).

The Hierarchy Tree

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.

Arrangement Dcel

The arrangement is parametrized with the interface class Dcel. The Dcel is a container class that defines the underlying combinatorial data structure used by the planar map. We define the concept ArrangementDcel_2 where the requirements for a Dcel class are defined.

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>

Models for an Arrangement Traits Class

We supply traits classes that support three families 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.