IntroductionAlgorithm MathsArea ToleranceStep by stepCodingReferencesHomepage |
## The Area Tolerance
- 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 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.
- 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.
- 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.
(AoEo)/N
Where
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.
(AoEo)/P
Where Again, the tolerance for k sides needs to be considered - it is
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 segmentThe 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 NotationThe 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. |
---|