Copyright © 2010-2022
License, terms and conditions
Clipper2 is an open source freeware 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:
Latest Version: 1.0.6
Last Update: 28 October 2022
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 coordinate points (vertices). Paths may be open (when their ends aren't joined) and are sometimes called polylines. Paths may also be closed with an implicit line segment joining the last vertex with the first. (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 clipping operations, subject paths may be open or closed, whereas clip paths must be closed. (The Clipper Library only supports clipping with closed paths.)
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 on signed 64bit integer coordinates internally. Because of this, the floating point coordinates accepted by ClipperD objects will be converted into integers using the floating point precision specified in ClipperD's constructor.
It's important to note that path coordinates can't use quite the full 64 bits (63bit signed integers) because the library needs to perform coordinate addition and subtraction. Consequently coordinates must be within ±4.6 × 1018 integer range, but this should be more that adequate to achieve any sensible degree of geometric precision.
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 touching polygons. If solutions aren't sufficiently simple, then a subsequent 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 their 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. This adds an Int64 Z member to vertex definitions (see Point64 and PointD). Z values can then be assigned to vertices prior to clipping. Further, during clipping, Z values can also be assigned to vertices created at path intersections via a user-defined ZCallback function. (Please note that these Z values are user defined, and they shouldn't be confused with 3D clipping.)
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-2022 Angus Johnson - Clipper2 1.0.6 - Help file built on 1 Nov 2022