## Problem Definition

Let **P **= {p_{1}, p_{2}, ..., p_{n}}
denote a polygonal chain of n vertices. A new chain is desired, called
a polygonal approximation, **A** = {a_{1}, a_{2}, ...,
a_{m}} where the following constraints must be satisfied:

- a
_{i} is in **P**, for all i= 1,...,m.
- a
_{1} = p_{1 }, a_{m} = p_{n};
The first and last points belong to the approximation chain.
- m <= n. The size of the approximation is not greater
than the original size.
- The distance
**D** between p_{i} (for all
i= 1,...,n) to the approximate polygonal chain **A** is less than or
equal to the error tolerance. We consider the error tolarance, denoted
by **W **and the distance criterion
used to determine **D,** as paramaters of the procedure.

#

### Reference

This applet is an implementation of the algorithm
described in :

__An iterative Procedure for the
Polygonal Approximation of Plane Curves.__

Author: Urs Ramer. Computer Graphics and Image Processing (1972) 1 (244-256)

extract from the abstract:

*"The approximation of arbitrary two-dimensional
curves by polygons is an important technique in image processing. For many
applications, the apparent ideal procedure is to represent lines and boundaries
by means of polygons with a minmum number of verticies and satisfying a
given fit criterion. (... )An apporximation algorithm is presented which
uses an iterative method to produce a small - but not minumum - number
of vertices that lie on the given curve. The maximum distance of the curve
from the approximated polygon is chosen as the fit criterion...."*