Robustness

In computational geometry, real values in polygon coordinates are always represented by discrete numbers, whether as integer or float variables. As a consequence, geometric computations won't be reliable (numerically robust) if they're premised on exact coordinates (eg at points of intersection). For example, imprecision must be anticipated when determining if a coordinate is exactly on a line segment, or if two coordinates are equal.

The Clipper library is numerically robust because it anticipates and manages coordinate imprecision. By using integer variables rather than floats, maximum imprecision is constant (since the imprecision of float values varies and is related to the size of each float value). And this simplifies differentiating significant from insignificant imprecision.

But not only is the imprecision of integer variables constant, the amount of imprecision relative to polygon size can be adjusted very easily through coordinate scaling. Clipper2 accepts coordinate values anywhere in the range ±4.6e+18 which accommodates coordinate scaling to very high degrees of precision.

Self-intersection artefacts


While issues related to using discrete numbers in geometric calculations are generally more obvious (ie more frequently encountered) when using integer coordinates, they are nevertheless still present when using float values. One issue that I alluded to above relates to assessing whether a vertex is left or right of a line segment.

Example 1


In the unscaled image below, the area of intersection of two polygons has been highlighted in bright green.


When we zoom in on the lowest point of intersection, in Clipper1 we'd find a tiny self-intersecting artefact there. This self-intersection would be present because the polygon wasn't split into two and the orientation of these vertices reversed once rounding was applied. (The three black dots highlight the 'real' unrounded points of intersection, and the red dots show where these three points are located once rounding is applied.). In Clipper2, this polygon is split into two polygons and the polygon with negligible area is discarded. In Clipper2, clipping solutions won't contain polygons where a number of vertices very close together would cause self-intersections.


Example 2


In this second example, 'union'ing the polygon above doesn't remove the tiny self-intersection that's there (at least without scaling). Because of rounding these tiny intersections aren't detected. With scaling however (eg × 100), this specific self-intersection is detected and tidied into 3 separate polygons. But even the most aggressive scaling won't entirely prevent tiny self-intersections. Nevertheless, with sensible scaling, these tiny self-intersections are unlikely to cause problems for the library user.

See Also

Union