Angus Johnson

Copyright © 2010-2023

License, terms and conditions

**Clipper2** is an **open source freeware** library 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:

- being able to clip complex self-intersecting polygons
- support polygons with multiple filling rules (EvenOdd, NonZero, Positive, Negative)
- is numerically robust, and
- is free to use in both freeware and commercial applications

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).

- Delphi: compiles with any version of Delphi back to
**Delphi 7**. - C#: core library uses
**Standard Library 2.0**but the sample code uses .NET5 - C++: requires
**C++17**but could easily be modified to C++11.

Latest Version: **1.2.2**

Last Update: 26 March 2023

**Download from GitHub**

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** are simply series of straight line **segments**. These are defined by series of 2D coordinates (points, vertices). Paths may be **open** (when their ends aren't joined) and are sometimes called **polylines**. Paths may also be **closed** with an explicit or implicit line segment joining 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 any polygons that aren't *simple*, either 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 usually 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, with complex polygons, additional information (i.e. a **filling rule**) is required to fully define which regions are filled, and which are not. In 2D graphics, there are two commonly used filling rules - *EvenOdd* and *NonZero*.

In closed paths, **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.

In *Clipper2* there are now two *Clipper* classes - **Clipper64** and **ClipperD**. *Clipper64* as it's name implies, supports 64bit integer coordinates, whereas *ClipperD* supports double float coordinates. Nevertheless, to ensure numerical robustness, *Clipper2* still performs all clipping operations using integer coordinates internally. Because of this, the floating point coordinates accepted by *ClipperD* objects will be scaled using the floating point precision specified in *ClipperD*'s constructor and then rounded into 64bit integers.

Nevertheless Path coordinates can't use quite the full 64bits (less 1 bit for the *sign*). At a minimum there must be room to perform integer addition and subtraction without overflow, so coordinates must remain within 62bits (±4.6 × 10^{18
}). Also, as coordinates extend beyond ~ ±1.0 × 10^{12
}, the algorithm that determines segment intersection points slowly degrades. While there are more accurate algorithms at the extremes of the coordinate range, they're a lot slower too (more info **here**). So, while ±4.6 × 10^{18
} is the hard limit for coordinate values, it's highly recommended that coordinates stay fairly close to ±1.0 × 10^{12
} range. Because of this, and because of a small cost in performance, the library does very little range checking. The range checking it does, is mostly linked to coordinate scaling, and will permit coordinates within ±4.6 × 10^{18
}.

Clipping operations wills 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 and inner 'hole' contours will wind clockwise (in Cartesian coordinates). And it also means that filling in clipping solutions will comply with any **FillRule** except **Negative** filling.

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 bring these solutions very close to their simplest forms.

The Clipper class's **PreserveCollinear** property only affects **closed paths**. Paths will sometimes contain consecutive collinear segments, where a 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, 180 degree 'spikes' will always be removed from closed solutions.

The library supports open path clipping, though only **subject** paths may be open. Given that open paths have no winding direction, vertex order in open path solutions will match the vertex order in their corresponding subject paths.

Open path clipping can also be performed concurrently with closed subject paths. Except in **union** operations, the presence of closed subject paths will have no effect on open path solutions. However, in **union** operations, open paths will be clipped wherever they overlap 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 clipping boundaries. In Clipper2, sometimes these segments will be included in clipping solutions, and sometimes not. When the adjacent (ie preceding and succeeding) segments are both inside or both outside the clipping region, then overlapping segments will be included or excluded respectively. However, for segments overlapping clipping boundaries with one adjacent segment inside and the other outside, their inclusion or otherwise in solutions remains undefined.

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.)

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**.

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.

**Index**, Changes, License, Clipper64, Clipper64.PreserveCollinear, Clipper64.ReverseSolution, Clipper64.ZCallback, Clipper.Offset, ClipperOffset, Clipper, InflatePaths, IsPositive, ClipType, EndType, FillRule, JoinType, Point64, PointD, USINGZ

Copyright © 2010-2023 Angus Johnson - Clipper2 1.2.2 - Help file built on 20 May 2023