Core Data Structures in the Clipper Library

The Clipper library is an open-source C++ toolkit designed for performing polygon clipping and offsetting operations. Within this library, points and polygons serve as fundamental data structures. Clipper primarily works with polygons and paths, where paths can represent either open polylines or closed polygons.

In Clipper, paths are typically represented as ordered collections of points. For open paths (polylines), the first and last points are distinct, while for closed paths (polygons), these points coincide to form a closed loop.

Clipper utilizes the Paths type to represent collections of one or more paths, which is essentially a std::vector<std::vector<IntPoint>>. Each inner std::vector<IntPoint> represents an individual path, with IntPoint being the library's defined point type containing integer coordinates (X, Y).

Although Clipper doesn't explicitly define a polyline structure, the Paths type can be used to represent collections of polylines. When creating a Paths object and populating it, each path (each inner std::vector<IntPoint>) can represent a polyline as long as the start and end points don't coincide, ensuring they're treated as open paths.

Representing Polylines with Paths

The following example demonstrates how to use the Paths type in Clipper to represent polylines:

#include <clipper.hpp>
#include <vector>

int main() {
    ClipperLib::Paths polylines; // Create a polyline collection (open paths)
    ClipperLib::Paths result;    // Container for operation results
    ClipperLib::IntPoint p1(10, 10);
    ClipperLib::IntPoint p2(20, 20);
    ClipperLib::IntPoint p3(30, 10);

    // Add a polyline to the collection
    polylines.push_back(std::vector<ClipperLib::IntPoint>{p1, p2, p3});

    // Perform Clipper operations like clipping or offsetting...
    // ...

    // Results will be stored in the result container

    return 0;
}

In this example, polylines is a Paths object containing a single polyline defined by three points. You can add additional polylines to the collection as needed, then apply various Clipper operations to process them, storing the results in result.

Point Representation

In Clipper, points are typically represented as structures or classes containing two floating-point values (usually double type) representing the X and Y coordinates. The exact implementation may vary between Clipper versions or custom implementations, but the fundamental concept remains consistent.

A simple point structure might look like this:

struct Point {
    double X;
    double Y;
};

Polygon Representation

Polygons in Clipper are represented as collections of points (std::vector<Point> or similar containers). These points are ordered according to their position along the polygon's boundary, forming the polygon's outline. The orientation of the polygon (clockwise or counter-clockwise) is important for certain Clipper operations, as it determines the polygon's "inside" and "outside".

A polygon structure might be implemented as:

#include <vector>

struct Polygon {
    std::vector<Point> vertices;
};

Alternatively, when directly using Clipper's provided types, you might use the library's Paths type, which is a std::vector<std::vector<IntPoint>>, where IntPoint is Clipper's integer coordinate point type.

Polyline Representation

In the Clipper library, polylines (also known as open paths or line sequences) can be represented similarly to polygons—as collections of points. Clipper doesn't explicitly distinguish between polygons and polylines; both are treated as collections of points. However, depending on how these points are used (e.g., as input or output for clipping operations) and their directional properties, they can be interpreted as representing either polygons or polylines.

To explicitly represent a polyline rather than a closed polygon, ensure that the provided point collection is not closed—the first and last points should not be identical.

When performing operations in Clipper, you may need to distinguish between open paths (polylines) and closed paths (polygons). This is typically achieved by ensuring the correct ordering of points and specifying whether paths are open or closed during operations. For example, when calling certain Clipper functions, you may need to pass a flag indicating whether the path is open or closed.

Key Terminology

Clipping

Clipping refers to the process of removing portions of a graphic that lie outside a specified region in a 2D plane. In the Clipper library, clipping operations are not limited to rectangular boundaries but can involve arbitrary polygons or even multiple polygons. Clipper supports four fundamental Boolean operations: intersection, union, difference, and XOR.

Code example demonstrating rectangular clipping with Clipper:

#include <clipper.hpp>
#include <vector>
#include <iostream>

int main() {
    ClipperLib::Paths subject, clip_boundary, output;
    ClipperLib::IntPoint p1(0, 0), p2(100, 0), p3(100, 100), p4(0, 100);
    subject.push_back(std::vector<ClipperLib::IntPoint>{p1, p2, p3, p4}); // Create a rectangle as the subject

    ClipperLib::IntPoint rect1(20, 20), rect2(80, 20), rect3(80, 80), rect4(20, 80);
    clip_boundary.push_back(std::vector<ClipperLib::IntPoint>{rect1, rect2, rect3, rect4}); // Create a clipping rectangle

    ClipperLib::Clipper clip_engine;
    clip_engine.AddPaths(subject, ClipperLib::ptSubject, true); // Add subject
    clip_engine.AddPaths(clip_boundary, ClipperLib::ptClip, true); // Add clipping boundary
    clip_engine.Execute(ClipperLib::ctIntersection, output); // Execute intersection

    // Output the clipping result
    for (const auto& path : output) {
        for (const auto& point : path) {
            std::cout << "(" << point.X << ", " << point.Y << ") ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Path

In the Clipper library, a path is an ordered collection of points that defines a contour. This contour can be an open path (like a line) or a closed path (like a polygon).

Line and Polyline

In Clipper, lines and polylines are synonymous terms referring to open paths with two or more points. A polyline consists of a sequence of points ordered along the path, with distinct start and end points.

Contour

A contour is synonymous with a path in the Clipper library and is used to represent the outer boundary or internal hole boundaries of a shape.

Hole/Inner Contour

In the Clipper library, holes or inner contours refer to closed regions within a polygon that are not part of the polygon's outer boundary. Inner contours are typically used to define voids within complex polygons.

Polygon Filling Rule

Polygon filling rules define which areas in a collection of closed paths are considered "inside" versus "outside". Clipper typically uses either the "Non-Zero Winding Rule" or the "Odd-Even Rule" to determine filled areas.