Introduction
Algorithm Maths
Area Tolerance
Step by step
Coding
References
Homepage

The Area Tolerance

The algorithm assumes the following

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

Lets say that the original polygon had an area of 100 units. We decide that we want the smoothed polygon to be no more than 10% bigger or smaller in area than the original. This means that the resultant smoothed polygon needs to have an area between 90 and 110 units in order to be acceptable.

Splitting the overall area tolerance over the entire polygon

An overall area tolerance is assigned to the polygon in percentage terms. This is called Eo. In our example then, Eo, the chosen tolerance on the area would be 10 units. If the notation becomes confusing, then see the section explaining notation.

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. For instance, when examining the very first step of the algorithm, it would be unwise to use the overall tolerance Eo as the area tolerance. This would lead to a very distorted figure. A better method is to spread the tolerance out over the polygon.

Note that in order to be consistent with the idea of a local area tolerance - all areas are computed with their sign, so that their additive effective on area is not incorrectly computed(i.e. sometimes area is added to the polygon, sometimes taken away - this needs to be accounted for). The different methods reviewed in the paper are outlined below.

  1. Perhaps the first way of splitting the tolerance over the whole polygon that springs to mind is to divide it over the number of points in the original polygon, i.e.

    2. Allowable Error E(u,1)= (AoEo)/N

    Where N is the number of points in the original polygon. Note that this suffices when eliminating 1 point. If we are merging k sides where k>2, (which the algorithm does if the area tolerance is not exceeded on the first iteration) then we use the following.

    E(k,1) = k*E(u,1) = k*E(k-1,1) + E(u,1)

    Here we note that E(k-1,1) was already computed as part of the last iteration, so the processor does not need to recompute it. This allows the algorithm an O(n) time complexity.

  2. The second strategy for spreading out the area tolerance is based on the tolerance per unit length of the boundary where P is the perimeter of the original polygon.

    3. Allowable Error E(u,2) = (AoEo)/P

    Where P is the perimeter of the original polygon.

    Again, the tolerance for k sides needs to be considered - it is

    E(k,2) = k*E(k-1,2) + E(u,2)*L(k)

  3. A third strategy was eventually used, but this is simply a combination of the two previous methods. According to Cordella and Dettori, it is easily demonstrated [1] that these methods are formally correct.

The combination of the two ends up being used in the algorithm and looks as follows.

E(k,3) = (E(k,1) + E(k,2))/2

Computing the area of a segment

The following equation is used to compute the area of the segment As shown in the diagram above, account is taken of the positive and negative areas.

Ak = 0.5*Sum of [(x(i) + x(i+1))*(y(i)-y(i+1))]......i=1 to k

A Brief word on Notation

The notaton used here is simple. E(u,1) represents the unitary(u) tolerance for all of the N sides of the polygon using the first strategy(hence the 1).

E(k,1) represents a tolerance value for a set of k points that are being merged. It can be represented by a multiplication, or iteratively with an addition to the previous sum.

E(u,2) is the unitary(u) tolerance obtained when using the second strategy(hence the 2).

E(k,2) is the tolerance for a set of k points that are being merged using the second strategy. It can be calculated iteratively. Note that L(k) represents the length of the kth segment to be merged.

E(k,3) then is the tolerance that the algorithm actually uses when merging k sides of the polygon together. It is a combination of the first two methods.