Crate polyclip

Expand description

Exact integer 2D polygon geometry.

polyclip provides robust polygon operations on integer coordinates: boolean operations (union, intersection, difference, xor) with arbitrary fill rules, N-ary unions, clipping of open paths, offsetting (polygons and open paths, all join and cap types), arc and circle approximation with a selectable error side, exact distance queries, point location, containment and intersection predicates, validity checks, fracturing into hole-free outlines, topology-preserving simplification, convex hulls and Minkowski sums.

It was written for the CAD tool cadlab (copper zone fills, DRC, silkscreen clipping, pad shapes, Gerber output) but has no domain-specific code.

use polyclip::*;

// A 10 mm square zone (nanometer units) minus two round obstacles grown by a clearance.
let zone = Ring::from([(0, 0), (10_000_000, 0), (10_000_000, 10_000_000), (0, 10_000_000)]);
let tol = ArcTol::new(1_000, Side::Outside);
let pads: Vec<Ring> = [(3_000_000, 3_000_000), (7_000_000, 6_000_000)]
    .iter()
    .map(|&(x, y)| Circle::new(Point::new(x, y), 500_000).to_ring(tol).unwrap())
    .collect();
let obstacles = offset(&pads, 200_000, Join::Round, tol).unwrap();

let fill: PolyTree = Boolean::new()
    .subject(&zone, FillRule::NonZero)
    .clip(&obstacles, FillRule::NonZero)
    .op(Op::Difference)
    .execute_tree()
    .unwrap();
assert_eq!(fill.polygons().count(), 1);

// Minimum-width enforcement, then Gerber-ready hole-free regions.
let fill = opening(&fill, 100_000, ArcTol::new(1_000, Side::Inside)).unwrap();
let regions: Vec<Ring> = fill.iter().map(|p| fracture(p).unwrap()).collect();
assert_eq!(regions.len(), 1);

// DRC: is a track closer than the clearance to a pad?
let track = Path::from([(0, 2_500_000), (10_000_000, 2_500_000)]);
assert!(distance_less_than(&track, &pads[0], 200_000));

§Number model

Coordinates are i64 (Point); every input and output coordinate must lie within ±MAX_COORD (2^40, about 1.1 km in nanometers). Fallible operations report out-of-range input as Error::CoordinateOutOfRange. Infallible queries (locate, intersects, contains, distance, area2, …) check the range and return a neutral result for out-of-range input (Outside, false, None, 0) rather than computing with overflowing arithmetic; in_range tells the cases apart.
All topological decisions (orientation, intersection, point location, distance comparisons) are computed exactly with i128 arithmetic (and a 384-bit product for squared distances). Floating point is used only to construct new vertices (arcs, offsets) and as a filter in front of exact fallbacks.
New vertices are integers. Boolean operations use snap rounding: every crossing is rounded to the nearest integer point (floor(v + 1/2) per coordinate) and every edge passing through the same unit pixel is routed through that point. Edges that are not moved by any rounding stay exactly where they were (so valid input passes through unchanged). No vertex moves by more than sqrt(2)/2, and the output is always valid: simple rings, no crossing edges, correct nesting.
Arc and offset vertices are computed in f64 (with the pure-Rust libm, identical on every platform) and rounded to the nearest integer point.

§Canonical output

Every polygon-producing operation returns canonical data, so results are deterministic and comparable with ==:

outer rings counter-clockwise, holes clockwise (Y-up: counter-clockwise means positive signed area);
no repeated consecutive vertices, no zero-length edges, collinear vertices removed (configurable on Boolean) except where needed to keep tags or shared vertices;
each ring starts at its lexicographically smallest vertex (min x, then min y);
holes sorted by vertex sequence, polygons sorted by their outer ring’s vertex sequence;
regions touching at a single point are separate rings (rings never share an edge);
bit-identical across platforms, runs and thread counts.

check_canonical verifies all of the above; validate checks validity of arbitrary input with a reason.

§Fill rules and orientation

Input rings may have any orientation, overlap and self-intersect. Winding numbers count counter-clockwise rings positively; FillRule (even-odd, non-zero, positive, negative) decides what is inside, separately for the subject and the clip operand.

§Vertex provenance (Z-tags)

Every input edge can carry a u64 tag (TaggedRing, TaggedPath, TaggedPolygon); untagged edges carry 0. Output edges keep the tag of the input edge they lie on, through booleans (Boolean::execute_tagged, Boolean::execute_tree), open path clipping (clip_paths) and offsets (offset_tagged). A vertex sits between two tagged edges, so a vertex created at an intersection records both source tags. Uses:

reconstruct arcs after booleans and offsets: tag the edges of each approximated arc with an arc id (Shape::to_tagged, offset_shape_tagged); consecutive output edges with the same id form one arc, which arcs_from_tags turns back into arc elements (emit them as single Gerber arcs);
explain results: “this fill edge comes from the clearance around U3 pad 7”.

§Robustness

No operation panics on any input: degenerate rings, collinear or duplicate points, coincident edges, zero area and huge vertex counts give a well-defined result or an error. The crate has no unsafe code and no global state; all types are Send + Sync. A Boolean engine can be cleared and reused across calls.

§Operations

Area	Items
Booleans	`Boolean`, `boolean`, `union_all`, `clip_paths`, `ZoneFill` (incremental)
Offsetting	`offset`, `offset_tree`, `offset_tagged`, `offset_paths`, `offset_shape`, `opening`, `closing`
Curves	`Circle`, `Shape`, `Curve`, `ArcTol`, `Side`, `arcs_from_tags`, `curved_boolean`
Queries	`locate`, `intersects`, `contains`, `area2`, `centroid`, `distance`, `distance_less_than`, `Prepared` (indexed, for repeated queries against one geometry)
Validity	`validate`, `validate_set`, `check_canonical`
Utilities	`fracture`, `simplify_polygons`, `triangulate`, `triangulate_delaunay`, `convex_hull`, `minkowski_sum`, `trapezoids`

§Features

serde: Serialize/Deserialize for all data types.
rayon: parallelize the heavy phases of booleans (noding, fragment merging and the sweep, by ranges of leaves, segments and vertical bands, as well as independent clusters of rings). Results are identical to the sequential build, for any number of threads.

Re-exports§

pub use boolean::Boolean;
pub use boolean::ClippedPaths;
pub use boolean::FillRule;
pub use boolean::Op;
pub use boolean::PathSource;
pub use boolean::RingSource;
pub use boolean::VertexVisitor;
pub use boolean::boolean;
pub use boolean::clip_paths;
pub use boolean::union_all;
pub use offset::EndCap;
pub use offset::Join;
pub use offset::closing;
pub use offset::offset;
pub use offset::offset_paths;
pub use offset::offset_paths_tagged;
pub use offset::offset_paths_tree;
pub use offset::offset_shape;
pub use offset::offset_shape_tagged;
pub use offset::offset_tagged;
pub use offset::offset_tree;
pub use offset::opening;

Modules§

predicates: Exact geometric predicates on integer points.

Structs§

ArcTol: Arc approximation tolerance: maximum deviation (sagitta) in coordinate units and side.
Boolean: Reusable boolean-operation engine.
Circle: A circle.
ClippedPaths: Result of clipping open paths by polygons.
Closest: Result of distance: the exact squared distance and a pair of closest points (one on each geometry, as f64 since they need not be integer points).
Path: An open polyline: consecutive vertices are joined, the last is not joined to the first.
Point: A point with integer coordinates.
PointF: A point with floating-point coordinates, used for results that are not representable on the integer grid (centroids, closest points).
PolyNode: One node of a PolyTree: an outer ring or a hole.
PolyTree: Full nesting of a polygon set: outer → holes → islands inside holes → …
Polygon: A polygon: one outer ring and zero or more holes.
Prepared: A geometry prepared for repeated queries: a spatial index over its segments and rings.
Rect: An axis-aligned rectangle with inclusive bounds.
Ring: A closed ring: consecutive vertices are joined and an implicit edge joins the last vertex to the first. The first vertex is not repeated at the end.
RingId: Identifies a ring: polygon index in the set (0 for a single polygon) and ring index within the polygon (0 = outer, 1 + i = hole i).
Segment: A line segment between two integer points.
Shape: A region bounded by curved contours: one outer contour and holes.
SqDist: An exact squared distance: the rational num / den.
TaggedPath: An open path whose edges carry user tags. tags[i] belongs to the edge points[i] -> points[i + 1], so tags.len() == points.len() - 1 (or 0 when empty).
TaggedPolygon: A polygon with tagged rings.
TaggedRing: A ring whose edges carry user tags (see the provenance section).
Trapezoid: A trapezoid of a vertical decomposition: the region with x0 <= x <= x1 between the lines supporting the bottom and top edges. Both edges span [x0, x1] and are given left to right, so the representation is exact (corners are generally not integer points).
Triangulation: A triangulation: vertices and counter-clockwise triangles indexing them.
ZoneFill: Incremental zone-fill engine: maintains zone − ⋃ obstacles while obstacles are inserted, removed and moved, recomputing only the regions a change can affect.

Enums§

Curve: One element of a Contour: a straight line or an arc to a new end point.
EndCap: How the ends of open paths are shaped.
Error: Errors returned by fallible operations.
FillRule: Rule deciding which regions are “inside” from their winding number.
Join: How offset edges are connected at convex corners.
Location: Where a point lies relative to a geometry.
Op: Boolean operation.
Side: Which side of the true curve the approximation may deviate to.
ValidityError: Why a polygon (set) is invalid.

Constants§

MAX_ARC_VERTICES: Maximum number of vertices generated for a single curve.
MAX_COORD: Largest supported absolute coordinate value: 2^40.

Traits§

Geometry: A geometry that queries (locate, intersects, contains, distances) accept.
PathSource: Anything that can be clipped as a set of open paths.
Preparable: Geometries that can be Prepared: Ring, Polygon, polygon sets, PolyTree, Path, Segment and Point. Sealed.
RingSource: Anything that can be fed to a boolean operation as a set of closed rings.

Functions§

arcs_from_tags: Rebuilds a curved contour from a tagged ring: maximal runs of consecutive edges whose tag maps to an arc centre (arc_of(tag) = Some(center)) become one Curve::CenterArc; every other edge becomes a Curve::Line.
area2: Twice the signed area of a geometry’s region (exact): the sum over its rings.
boolean: Computes subject op clip with one fill rule for both operands.
centroid: Area centroid of a region given as rings (holes clockwise subtract), or None when the area is zero. Computed in f64 from exact per-edge terms, relative to the first vertex.
check_canonical: Checks that a polygon set is valid and in the canonical form produced by this crate: outer rings counter-clockwise and holes clockwise, every ring starting at its lexicographically smallest vertex, holes sorted, polygons sorted by outer ring, and (when collinear_removed) no vertex collinear with its neighbours unless it is shared with another ring.
clip_paths: Clips open paths against the region of clip (under rule), splitting them into the parts inside and outside.
closing: Morphological closing: grow by d, then shrink by d, with round joins. Fills gaps and notches narrower than 2 * d.
contains: true when every point of b belongs to a (closed sets), exactly.
convex_hull: Convex hull of a point set (Andrew’s monotone chain, exact).
convex_hull_of: Convex hull of every vertex of a geometry (rings, polygons, paths, …). See convex_hull.
curved_boolean: Boolean operation on curved shapes that keeps arcs as arcs.
distance: Exact minimum distance between two geometries, with a pair of closest points. None when either geometry is empty or has coordinates outside ±MAX_COORD.
distance_less_than: true when the distance between the two geometries is strictly less than d. false for empty geometries and for coordinates outside ±MAX_COORD.
distance_sq: Exact squared minimum distance between two geometries (None when either is empty).
fracture: Fractures a polygon into a single outline: its holes are joined to the outer ring by zero-width cut-ins, as required for Gerber regions.
fracture_set: Fractures every polygon of a set (see fracture).
in_range: true when every coordinate of g lies within ±MAX_COORD (vacuously for an empty geometry).
intersects: true when the two geometries share at least one point (closed sets).
locate: Location of p relative to g.
locate_in_polygon: Location of p relative to a polygon (inside its outer ring and outside all holes).
locate_in_ring: Location of p relative to the region bounded by a ring (non-zero winding rule; for simple rings this is the usual interior).
minkowski_sum: Minkowski sum A ⊕ B = { a + b : a ∈ A, b ∈ B } of two polygons (with holes), exact.
offset: Offsets a region by delta (positive grows, negative shrinks). See offset_tree.
offset_paths: Offsets open paths. See offset_paths_tree.
offset_paths_tagged: Offsets open paths with edge tags (see offset_tagged for the tagging rules; end caps are tagged corner_tag). Returns the nesting tree.
offset_paths_tree: Offsets open paths by delta >= 0 on both sides (strokes them with width 2 * delta), with join at interior vertices and cap at both ends. Returns the nesting tree.
offset_shape: Offsets a curved Shape by delta.
offset_shape_tagged: Like offset_shape, with edge tags: edges coming from element j of contour i (0 = outer, 1 + k = hole k) are tagged tag(i, j), corner joins corner_tag.
offset_tagged: Offsets a region by delta, propagating edge tags, and returns the nesting tree.
offset_tree: Offsets a region by delta (positive grows, negative shrinks), returning the full nesting tree.
opening: Morphological opening: shrink by d, then grow by d, with round joins. Removes every part narrower than 2 * d (minimum-width enforcement for copper zones) while leaving wide parts essentially unchanged (convex corners get rounded with radius d).
ring_area2: Twice the signed area of a ring given as a vertex slice (exact, shoelace formula). Positive for counter-clockwise rings. Returns 0 for rings with fewer than three vertices or with coordinates outside ±MAX_COORD (whose area could not be computed exactly).
ring_winding: Winding number of pts (a closed ring) around p, or None when p is on the ring.
simplify_path: Simplifies an open path with the Douglas–Peucker algorithm.
simplify_polygon: Simplifies a single polygon, preserving its topology.
simplify_polygons: Simplifies every ring of a polygon set with a topology-preserving Douglas–Peucker algorithm, considering all rings together.
trapezoids: Vertical decomposition of the region of input (non-zero fill rule) into trapezoids.
triangulate: Triangulates a polygon with holes.
triangulate_delaunay: Constrained Delaunay triangulation of a polygon with holes.
triangulate_set: Triangulates a set of polygons with pairwise disjoint interiors (they may touch at vertices) into one triangulation sharing vertices between polygons.
union_all: N-ary union of all rings in one pass, under rule. Also normalizes arbitrary (self-intersecting, overlapping, any orientation) rings into a canonical polygon set.
validate: Checks that a polygon is valid: every ring simple with at least three vertices and non-zero area, holes strictly inside the outer ring and with disjoint interiors, rings touching only at isolated points without disconnecting the interior. Orientation is not checked (see check_canonical).
validate_set: Checks a polygon set: every polygon valid (see validate) and polygon interiors pairwise disjoint (touching at isolated points is allowed, sharing edges is not).

Type Aliases§

Contour: A closed contour made of lines and arcs. Each element starts where the previous one ends; the first element starts at the end of the last one.
PolygonSet: A set of polygons with disjoint interiors (a “multipolygon”).
Result: Result alias.
VertexVisitor: Callback receiving a vertex sequence and its optional per-edge tags.

Crate polyclip

Crate polyclip Copy item path

§Number model

§Canonical output

§Fill rules and orientation

§Vertex provenance (Z-tags)

§Robustness

§Operations

§Features

Re-exports§

Modules§

Structs§

Enums§

Constants§

Traits§

Functions§

Type Aliases§

Crate polyclip