Approximation of Curves

1. Piecewise linear approximation of parametric curves

As part of her Diploma thesis, Ekaterina Langer developed CGAL-based software for approximating a single curve given in parametric form, by a polygonal arc. For special parametrizations like B-splines and Bézier curves, it is possible to have a guaranteed approximation with some given error tolerance. For general curves, an error bound can only be given if information about the second derivatives (curvature) is available.

2. Piecewise linear approximation of piecewise curves

The classical algorithms for curve simplification take a polygonal arc as input and produce another polygonal arc with fewer vertices. An implementation of these algorithms is being prepared by Ovidiu Grigore and Remco Veltkamp at Utrecht University as a CGAL extension package.
The current piece of software extends these algorithms to curves which are composed of curved pieces. More details describing the program can be found in the accompanying technical report.

The classical algorithms use just a few primitive operations:

In addition, the following operation is convenient: So far, we have extended the Douglas-Peucker algorithm to this setting. The software is generic: It can treat all curves which are composed of pieces for which the first two operations above can be supplied. As a first prototype class of such curves, we have implemented curves consisting of straight segments and circular arcs. It is planned to integrate the work on parametric curves (item 1) into this setting.