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

Chapter 24
2D Arrangements

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

Introduction

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

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:

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.