In computational geometry, polygon coordinates are always represented by discrete numbers, whether as integer or float variables. And quite often these coordinate values differ from their real values. While geometric imprecision is usually more obvious when using integer coordinates, it still occurs when using float values. And if this imprecision isn't anticipated and handled properly, geometric computations won't be reliable (numerically robust). For example, some imprecision must be expected when calculating where line segments intersect.
Imprecision associated with float variables (whether single or double type) will vary considerably depending on the size of their contained values. But integer imprecision will always be constant (±1 unit). And since it's much easier to differentiate significant from insignificant imprecision with integer coordinates, the Clipper library uses these internally for all geometric calculations. Because the Clipper library avoids calculations that assume exact coordinates, it is numerically robust.
Caution: Since integer imprecision is ±1 unit, the library user shouldn't expect solutions to contain polygons with near zero areas. For example, a triangle in a solution with an edge that's only 1 unit in length will be considered within a rounding adjustment of having zero area. These near zero area polygons will be removed from solutions. So it's important that library users appropriately scale paths in clipping operations when you would otherwise expect polygons with very small areas. (Alternatively, use the PathsD structure instead of Paths64 when clipping, since the library will perform the required scaling internally.)
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 in the clipping solution. This self-intersection occurs because 1. the polygon wasn't split into two polygons, and 2. the orientation of the 3 lowermost vertices is reversed due to vertex rounding. (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 first split into two polygons, and since the smaller polygon has negligible area, it's discarded from the solution.
Performing a union operation on this second polygon won't remove its two tiny self-intersections because they won't be detected due to rounding. With scaling however (eg × 100), these self-intersections will be detected and the polygon will be transformed into 3 separate polygons. But even the most aggressive scaling won't prevent self-intersections occurring on (relatively rare) occasions. Nevertheless, with sensible scaling, these tiny self-intersections are unlikely to cause problems for the library user.
Copyright © 2010-2024 Angus Johnson - Clipper2 1.3.0 - Help file built on 14 Jan 2024