Make your own free website on Tripod.com




Introduction
Algorithm Maths
Area Tolerance
Step by step
Coding
References
Homepage

Mathematical operation of the Algorithm

The algorithm is iterative(i.e. it repeats itself until a suitable solution is computed). A point X is chosen at random from the N points that make up the polygon. Point X has two adjacent points. The algorithm proceeds to remove one of the adjacent points of X and computes the area of the new polygon. We assume that the point adjacent and anti-clockwise is removed. There are (N-1) points in this new polygon. This is where we now check our area tolerance, which is divided out over the N points. More about the area tolerance later.

If the area of this polygon is within the tolerance selected, then we take off the next anti-clockwise point and recalculate the area of the new polygon. Again, we check if the area tolerance is exceeded. If not, the process continues until the tolerance is finally exceeded.

Once the tolerance has been exceeded, the algorithm backtracks, and the previous point is selected(X1) as a point of the resultant desired polygon. There are now two points selected for the final smoothed shape, [X,X1]. Continuing anti-clockwise, the algorithm restarts with X1 as the starting point. The process repeats itself until all N points have been considered. The resulting set of points make up the smoothed polygon.

The above method is very simple, but it requires special consideration of the area tolerance. It also assumes that the area of the original polygon is known, along with all the vertices, and that sequential collinear points are removed. These are all assumed as having taken place prior to the algorithm being performed on the set of data.