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