## Problem Definition

Let P = {p1, p2, ..., pn} denote a polygonal chain of n vertices. A new chain is desired, called a polygonal approximation, A = {a1, a2, ..., am} where the following constraints must be satisfied:

• ai is in P, for all i= 1,...,m.
• a1 = p1 , am = pn; 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 pi (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...."