Error Control

Numerical roundoff errors, and the numerous sliver polygons generated even if there is no roundoff, help make the polygon overlay problem so hard. With OVERPROP, slight errors in calculating intersections vertex coordinates will cause proportionally slight errors in the areas. OVERPROP also does not care about roundoff errors that cause one chain of edges to cross another erroneously as shown in figure 6. This will either cause the output to be off by an amount proportional to the geometric error in spite of this topological error, or it will create a spurious new object and report it with an insignificant area.

=4in

  
Figure 6: Topological Error Caused by Numerical Inaccuracy

However, although OVERPROP does not explicitly use the topology of the polygons, it implicitly assumes that it is topologically clean, or consistent in the following ways.

• There are no missing edges, and no gaps between edges of a polygon.
• The polygon names stored with the edges are all correct.

In fact the sensitivity of OVERPROP to these input errors may be used approximately to test for consistency by the following method.

1. Repeatedly randomly translate and rotate the input maps.
2. Find the areas with OVERPROP.
3. If the answers are different by more than numerical roundoff, then the input is bad. If the answers agree after several random operations, then the input is almost certainly internally consistent.