# This page under Construction

This tutorial is being 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.
If you're looking at this Prof. Toussaint - I sent you an e-mail last week asking for that extension - I'll be working on this very hard over the next few days and hope to have things in shape by Monday the 4th of May. The tutorial is layed out as follows.

## 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

Piecewise linear approximation of digital curves is a useful technique
in many pattern recognition tasks. The objective is to represent a
digital curve by a sequence of segments, whereby the obtained polygon
preserves the original shape and size to a specified tolerance.
This method is useful for preprocessing for the following reasons

- It eliminates noise and redundant data.
- It allows for subsequent processing to be simpler and more efficient.

## Basis of the Algorithm - Tolerance Evaluation

Cordella and Dettori's algorithm is an iterative one, based on scale-
independent appoximation criterion. The tolerance on the smoothing is
given as a percentage of the original polygon area. The algorithm is
thus area-preserving. Thus, in the case of picture processing, each
object is assigned its own area tolerance. This prevents objects being
assigned unsuitable tolerances. If a picture consisted of 2 shapes,
one large, and one small, then it would not be appropriate to assign
the same absolute tolerance to both, but a percentage area of each
object solves the problem.

The algorithm assumes the following

Area Ao of the polygon to be smoothed is known.
All N vertices of the polygon are available.

There are different acceptable methods of assigning an area tolerance.
This is because a polygon may well be characterized by both number of
sides and by the length of these sides.

Consider the following.

An area tolerance is assigned to the polygon in percentage terms.
This is called Eo.

The more formal definition is Eo : the a priori estimate
of the maximum percentage area variation which can be admitted.

Thus, the numerical value of the tolerance is simply

Allowable Error = (AoEo)/N

Animated GIF from: