Converting from planar polynomial domain to planar polygon

Question

Let's assume we have a planar domain whose boundary can be described with a polynomial curve (like Bezier curves). Now assume that you want to produce a discretization of the boundary, i.e. you want to produce a polygon by sampling the polynomial defining the boundary of the domain. How can I produce a boundary that incurs in a error lower than some user provided tolerance? A measure of the error could be something like.

$$ \sum_{\text{sides}}\int_0^1 ||\operatorname{line}(x_j,x_{j+1},t) - \partial\Omega_j(t)||^2 dt $$

That is, the square error of the polygon (whose sides are straight lines from vertex $x_i$ to $x_{i+1}$) with respect to the polynomial domain whose sides are represented by the parametrization $\partial\Omega_j(t)$. Each side is parametrized in the interval $t \in [0,1)$.

I am trying to improve the shape2polygon function of the GNU/Octave package geometry.

EDIT: The idea is to produce a polygonal representation of the original domain with the given error, with as few vertices as possible.

Thanks

EDIT:

• I have implemented an GNU/Octave non-recursive version of the Ramer-Douglas-Peucker algorithm to simplify polylines and polygons. simplifyPolyline_geometry.m and simplifyPolygon_geometry.m.
• I have implemented an GNU/Octave non-recursive version of the algorithm in L. H. de Figueiredo (1993). "Adaptive Sampling of Parametric Curves". Graphic Gems III. This function performs adaptive sampling of a parametrized planar curve. curve2polyline.m. The extension to polynomial domains is in shape2polygon.m.

Answer 1

You want to perform an adaptive sampling of the boundary curve.

For Bézier curves, use the de Casteljau algorithm recursively until the control points are approximately collinear. See for instance Adaptive Subdivision of Bezier Curves from the Anti-Grain Geometry project.

For general curves, see for instance Adaptive sampling of parametric curves, in Graphics Gems V, 1995.

Answer 2

The problem of simplifying a polygon is well-studied. The Douglas-Peucker algorithm is among the most popular methods. It can be implemented to run in time O(n log n). See the Wikipedia article on this algorithm.

Answer 3

The question to me is simply whether you want to have the minimal number of vertices, or whether you're just interested in a small number of vertices.

I'd use the obvious, greedy adaptation algorithm: you start with a small number of vertices and get a poor boundary approximation. Let's say you have $N$ segments in this step. Then for each segment $i,i=1\ldots N$ of your polygonal approximation, you compute the error $e_i$ of this one segment, and if $e_i>\frac{tol}{N}$ then you insert a new vertex along the boundary and split the segment into two. Iterate this until all segments have an error less than $\frac{tol}{N}$ and you have a boundary approximation with an overall error equal to or less than $tol$.