Introduction Algorithm Maths Area Tolerance Step by step Coding References Homepage	An O(N) Algorithm for Polygonal Approximation This webpage shall contain an explanation of a sequential algorithm used for polygonal approximation of plane, closed curves, which was presented in a 1985 paper by L.P. Cordella(University of Naples, Italy), and G.Dettori (Institue of Applied Mathematics of C.N.R., Geneva, Italy). Introduction This tutorial was developed as part of a Pattern Recognition course(308-644B) given by the McGill University School of Computer Science . The course lecturer is Godfried Toussaint. Piecewise linear approximation of digital curves is a useful technique in many pattern recognition tasks. The objective is to take a polygon represented by a large number of points and represent it by fewer points while preserving certain characteristics of the polygon. In this algorithm the area of the polygon is preserved to within a chosen tolerance. Preserving the area of a polygon is often desirable for instance in the case of picture processing. Often there are several objects being smoothed, some large, some small. If an absolute area tolerance were assigned to the picture, then some objects might disappear entirely. The smaller fish in the photograph opposite might disappear altogether. Clearly then, it is more prudent for each object to be assigned a tolerance suitable to its dimensions. Assigning a tolerance based on percentage area achieves this objective, and is the basis for the algorithm. Algorithms like this are used in pre-processing of data because They eliminate noise and redundant data. They allow for subsequent processing to be simpler and more efficient.

Introduction
Algorithm Maths
Area Tolerance
Step by step
Coding
References
Homepage

An O(N) Algorithm for Polygonal Approximation

This webpage shall contain an explanation of a sequential algorithm used for polygonal approximation of plane, closed curves, which was presented in a 1985 paper by L.P. Cordella(University of Naples, Italy), and G.Dettori (Institue of Applied Mathematics of C.N.R., Geneva, Italy).

Introduction

This tutorial was developed as part of a Pattern Recognition course(308-644B) given by the McGill University School of Computer Science . The course lecturer is Godfried Toussaint.

Piecewise linear approximation of digital curves is a useful technique in many pattern recognition tasks. The objective is to take a polygon represented by a large number of points and represent it by fewer points while preserving certain characteristics of the polygon. In this algorithm the area of the polygon is preserved to within a chosen tolerance.

Preserving the area of a polygon is often desirable for instance in the case of picture processing. Often there are several objects being smoothed, some large, some small. If an absolute area tolerance were assigned to the picture, then some objects might disappear entirely. The smaller fish in the photograph opposite might disappear altogether. Clearly then, it is more prudent for each object to be assigned a tolerance suitable to its dimensions. Assigning a tolerance based on percentage area achieves this objective, and is the basis for the algorithm.

Algorithms like this are used in pre-processing of data because

They eliminate noise and redundant data.
They allow for subsequent processing to be simpler and more efficient.

Animated GIF from: