 Introduction
Algorithm Maths
Area Tolerance
Step by step
Coding
References
Homepage # Coding of the Algorithm

Coding the algorithm involves the use of several variables defined as follows
• Ao, the Initial Area of the Polygon
• Eo, the desired maximum error
• Eu, the error associated with a given iteration of the algorithm
• Ek, the local tolerance
• Ak, the local area error
• Ko, K, the indices of the extreme points of an approximating segment
• N, the number of points in the algorithm
Note that some pre-processing of the points in the polygon is desireable, specifically ensuring that three consecutive vertices are never collinear in order to avoid zero area being computed.

### Step 1 - initializing the algorithm

Calculate the overall area tolerance : Eo*Ao
Next, compute E(u,1) and E(u,2) the allowable error associated with each side of the polygon using the equations detailed in the Area Tolerance section of this tutorial.
E(u,1) = Ao*Eo/N
E(u,2) = Ao*Eo/P

### Step 2

Next, get the points which form a segment - randomly choose a starting point, let this be Ko, then choose the third point clockwise or anticlockwise to be K. This gives us our first line segment, [KoK]
Initialise Ek and Ak to zero - these will be calculated in Step 3.

### Step 3

WHILE K<=N (*this section makes the approximating segment larger until the area tolerance is exceeded*)
1. Update Ek
2. Update Ak
3. IF Ak<=Ek THEN let K+1=K (* extending the approximating segment)
ELSE (*area tolerance exceeded*)
1.Make point K-1 part of the smoothed polygon
2.Reset the approximating segment, let Ko = K-1; let K=K+1
3. Initialise Ek and Ak to zero again.
END
END

Output(K-1)th point.( * this is the last part as the number of points in the line segment has reached the number of points in the polygon *)

EXIT  