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:
- find the farthest point of a piece of a curve from a given line or
line segment
- split a piece of a curve at a given point
In addition, the following operation is convenient:
- When the approximation has been sufficiently refined so the there is
only a single piece of curve under consideration, one might resort to special
approximation methods for this class of curves, as described in item 1 above.
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.