Arrangements on Parametric Surfaces I: General Framework and Infrastructure

We introduce a framework for the construction, maintenance, and manipulation of arrangements of curves embedded on certain two-dimensional orientable parametric surfaces in three-dimensional space. The framework applies to planes, cylinders, spheres, tori, and surfaces homeomorphic to them. We reduce the effort needed to generalize existing algorithms, such as the sweep line and zone traversal algorithms, originally designed for arrangements of bounded curves in the plane, by extensive reuse of code. We have realized our approach as the Cgal package Arrangement_on_surface_2. We define a compact and modular interface for our framework; for a given application a required small subset of the interface can be identified. Then, only this subset must be implemented. A companion paper describes concretizations for several types of surfaces and curves embedded on them, and applications. This is the first implementation of a generic algorithm that can handle arrangements on a large class of parametric surfaces.