![]() |
Overview | ![]() |
By using integer coordinates for all polygons, the Clipper Library has side-stepped the thorny issue of numerical robustness that otherwise plagues geometric computations with floating point values. However, rounding polygon coordinates to integers introduces its own complications.
It is important to stress at the outset that there is unavoidably a small degree of imprecision in the coordinates returned by Clipper, and that coordinates may be up to ½ a unit distant from their true positions. Fortunately, this rounding imprecision is easily managed by appropriate scaling.
The image on the right shows an example of where rounding might produce unexpected results. Here two polygons (triangles) are being merged with a 'union' operation. The region shaded green represents the 'merged' polygon returned by Clipper. It's evident that the bottom-left polygon from the input is missing from the result.
This is perhaps best explained by a very simple overview of how the clipping algorithm is implemented. Imaginary horizontal lines (called scanlines) pass through each and every vertex in the supplied set of polygons (ie both subject and clip polygons). The regions between adjacent scanlines are called scanbeams. Scanbeams are processed in order, starting with the bottom-most scanbeam and proceeding to the top-most. For each scanbeam there is a set of 'active' edges, that is those edges that pass through that scanbeam. The relative positions of active edges at both the bottom and top of a given scanbeam are used to determine the locations of intersections within a scanbeam. Therefore it's necessary to determine the relative coordinates of each edge at each scanline. Since coordinates are rounded into integer values, edges can be 'repositioned' up to ½ a unit horizontally away from their true positions at any given scanline.
In the image on the right the edge (2,5) -> (1,3) is repositioned through rounding to (2,4) at scanline Y=4. This repositioning reduces the bottom-left polygon's area to zero and it is discarded.
If precision greater than ½ a unit is desired, then polygons should be scaled up (eg by a factor of 2 or 10) and the resulting polygons returned by Clipper scaled down by this same factor.
This second image is a 30X 'close up' of the first image focusing on the points of intersection. The three 'black dots' highlight the actual points of intersection (with their fractional coordinates displayed). The smaller 'red dots' show where these points of intersection will be moved to when rounding is applied. With a little care you should be able to see how rounding in this example reverses the orientation of these vertices causing a 'self-intersection artefact'.
Although self-intersection artefacts are always tiny (having sub-unit dimensions) they can cause problems if they're ignored and polygons are assumed to be 'simple'.
Since Clipper's Orientation function uses the orientation of the three bottom-most vertices of a polygon to determine the orientation of the whole polygon, Clipper takes special care to remove any 'self-intersection artefacts' that would otherwise occur at the bottom of output polygons. However, self-intersections can still occur occasionally in other locations as the following example will demonstrate.
In this final example the single polygon on the left has a tiny self-intersection that isn't detected by Clipper. Due to rounding, the vertex (88,50) appears to simply 'touch' rather than cross over (by a tiny fraction) the right edge of the polygon.
Copyright ©2010-2012 Angus Johnson - Clipper version 4.9.7 - Help file built on 29-November-2012