Rounding

In computational geometry, polygon coordinates are always represented by discrete numbers, whether they be integer or float variables. Consequently, geometric computations won't be reliable (numerically robust) if they're assuming exact coordinates (eg at points of intersection), especially when comparing coordinates.

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

Not only is the imprecision of integer variables constant, its size 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.

Finally, because imprecision can bring together coordinates that aren't strictly identical, the library uses additional calculations to check relative positioning.

Of course problems related to moving real coordinates to discrete ones isn't caused by rounding as the heading implies. But value imprecision is implicit in rounding and Clipper uses rounding internally in all clipping operations.

Self-intersection artefacts


Yet despite carefully preserving numerical robustness, there's another problem associated with using discrete numbers. Coordinate imprecision will very occasionally cause the library to return tiny self-intersection artefacts as explained below.

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 with aggressive scaling there can be occasions when tiny self-intersections aren't detected, even though they'd have to be very much smaller relative to their unscaled polygons. Nevertheless these tiny self-intersections aren't likely to cause problems for the library user.

See Also

Union