Clipper2 - Polygon Clipping and Offsetting Library

Clipper2 is an open source freeware software library (written in C++, C# and Delphi Pascal) that performs line and polygon clipping, and offsetting.

Clipper2 is a major update of my original Clipper library which I'm now calling Clipper1. Clipper1 was written over 10 years ago and although it still works very well, Clipper2 is much better. And Clipper2 has all the features of Clipper1 that sets Clipper apart from other polygon clipping libraries, including:

Source Code and Compilers:

The Clipper library is maintained in three languages - C++, C# and Delphi Pascal. While I do most of the library's development in Delphi, I've made a habit of translating it into C++ and C# as a way of developing my skills in these languages too. And as a side benefit, I often find bugs while making these translations.

The C++ code also contains a header file that exports virtually all of the library's features via simple functions. So by compiling this header into a DLL or shared object, the library can be accessed by almost any programming language. And when performance is critical, Delphi and C# users may even prefer accessing the library this way since it'll be faster than the C# or Delphi compiled code (see chart here).

Download:

Terminology:

Originally clipping referred to the process of removing or "cutting away" parts of images that were outside a rectangular clipping window. However over time this process has been generalized to include clipping with non-rectangular windows, and to include union, difference and XOR boolean operations too. And in this library, instead of raster images being clipped, vector paths (subjects) are clipped with other (clip) vector paths that define the clipping regions.

Paths (see Path64 & PathD) are simply series of straight line segments. These are defined by series of 2D coordinates (aka points or vertices). Paths are open when their ends don't join together. And open paths are sometimes called polylines. Paths are closed when their ends do join (with an implicit line segment between the first and last vertices). Only context will determine whether paths are open or closed. Closed paths are often called polygons, but more accurately, they are simply the contours that outline polygon regions (see below). In this clipping library, subject paths in clipping operations may be open or closed, whereas clip paths must be closed.

Simple polygons are formed by single closed paths that don't self-intersect. Complex polygons are polygons that aren't simple, whether because they self-intersect or because they require more than one path to define their enclosed "filling" regions. Polygon holes are any regions inside polygons that aren't filled. Holes are defined by inner polygon contours that are separate from and inside outer polygon contours. While the filling region of a simple polygon is unambiguous, the filling region of a complex polygon is not. So complex polygons require additional information (i.e. a filling rule) to fully define which regions are filled, and which are not. In 2D graphics, there are two commonly used filling rules - EvenOdd and NonZero.

Closed path segments are commonly referred to as edges. Edges are considered touching when they are collinear and overlap, and polygons are touching when they have touching edges.

C++ Example:

  #include "clipper2/clipper.h"
  #include <iomanip> 
  using namespace Clipper2Lib;
  using namespace std;  
  PathsD subject = {{{100,50},{9.5,79.4},{65.5,2.4},{65.5,97.6},{9.5,20.7}}};
  PathsD clip = {{{20,20},{80,20},{80,80},{20,80}}};
  PathsD solution = Intersect(subject, clip, FillRule::NonZero);
  cout << setprecision(3) << solution << endl;

Console output:
65.5,38.8, 80,43.5, 80,56.5, 65.5,61.2, 65.5,80, 52.7,80, 44.1,68.2, 20,76, 20,65, 30.9,50, 20,35, 20,24, 44.1,31.8, 52.7,20, 65.5,20

Coordinate Range:

In Clipper2 there are now two Clipper classes - Clipper64 and ClipperD - that perform all clipping operations. While Clipper64 accepts Path64 paths, and ClipperD accepts PathD paths, both these classes still perform clipping operations using integer coordinates internally. This is to ensure numerical robustness. Because of this, ClipperD performs double / integer conversions before and after clipping (by scaling and de-scaling coordinates using the specified decimal precision).

Even though Path64 paths can be assigned using all 64bits, clipping can't be performed using quite this full range. At a minimum there must be room to allow integer addition and subtraction without overflow. To accommodate this (and the sign bit too), coordinates must at the very least remain within 62bits (±4.6 × 10¹⁸). However, as coordinates extend beyond ±1.0 × 10¹⁵, the algorithm that determines where segments intersect slowly degrades. (There are algorithms that are more accurate at the extremes of the coordinate range, but these algorithms are also significantly slower.) Given this flexibility in ranges, and because range checking will affect performance, all range checking is left to the discretion of the library user.

Clipping closed paths:

Clipping operations will always return Positive oriented solutions (unless the Clipper object's ReverseSolution property has been enabled). This means that outer polygon contours will wind anti-clockwise (in Cartesian coordinates), and inner hole contours will wind clockwise. And because paths in clipping solutions never intersect, both EvenOdd and NonZero filling would correctly apply to the solution, though it's usual to apply the same FillRule that was applied to the subject and clip paths during clipping.

A lot of effort has gone into returning solutions close to their simplest forms, but there's no way to do this perfectly without significantly degrading performance. So there will, on occasions, be solutions with polygons that are touching. If this is problematic, then a follow up union operation will frequently bring these solutions to their simplest forms.

The Clipper class's PreserveCollinear property only is only relevant when clipping closed paths. Paths will sometimes contain consecutive collinear segments, where the shared vertex can be removed without altering path shape. Removing these vertices simplifies path definitions and is generally (but not always) preferred in clipping solutions. Nevertheless, where consecutive collinear segments create 180 degree 'spikes', these will always be removed from closed solutions.

Clipping open paths:

The library supports open path clipping, and this may also be performed concurrently with closed path clipping. However, only subject paths may be open. Except in union operations, the presence of closed subject paths will have no effect on open path solutions. In union operations, open paths will be clipped wherever they overlap any closed paths (regardless of whether they are subject or clip paths).

Unlike closed path clipping, there's not always an obvious or right way to clip open path segments when they overlap (are collinear with) clipping boundaries. Sometimes these segments will be included in clipping solutions, and sometimes not. When the adjacent (ie preceding and succeeding) segments of an overlapping segment are both inside the clipping region, then the overlapping segment will be included. When adjacent segments are both outside, then the overlapping segments will be excluded. When one adjacent segment is inside and the other is outside, then the overlapping segment will be included when the lower-most adjacent segment in inside the clipping region.

Adding user-defined data to clipping paths:

With regard to clipping solutions, occasionally users will need to assign user-defined data to vertices, including those created at path intersections. To facilitate this, the pre-processor directive USINGZ can be set that adds an Int64 Z member to vertex definitions (see Point64 and PointD). Z values can then be assigned to vertices prior to clipping, and during clipping with newly created vertices at points of intersection (ie via a user-defined ZCallback function). Note however, that these Z values are user defined values and shouldn't be confused with 3D geometries and 3D coordinates.)

Polygon Offsetting:

Geometric offsetting refers to the process of creating parallel curves that are offset a specified distance from their starting positions.

While all offsetting is performed by the ClipperOffset class in the Clipper.Offset unit, the complexities of constructing and using this class can usually be avoided by using instead the InflatePaths function in the Clipper unit. This function can both inflate and shrink polygons (using positive and negative offsets respectively). Offsetting can be performed using a number of JoinTypes and EndTypes. While both open paths and closed paths can be offset, logically only closed paths can be shrunk (ie with negative offsets).

Note: Offsetting shouldn't be confused with the process of polygon translation.

References:

The Library is based on but significantly extends Bala Vatti's polygon clipping algorithm as described in "A generic solution to polygon clipping", Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63.

A section in "Computer graphics and geometric modeling: implementation and algorithms" by By Max K. Agoston (Springer, 2005) discussing Vatti Polygon Clipping was also helpful in creating the initial Clipper implementation.

The paper titled "Polygon Offsetting by Computing Winding Numbers" by Chen & McMains (Paper no. DETC2005-85513, ASME 2005. Pages 565-575) contains helpful discussion on the complexities of polygon offsetting together with some solutions.