Make your own free website on Tripod.com




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