knipsa 0.2.1

Polygon booleans, offsets, point queries, and triangulation in Rust
Documentation

knipsa

CI

A crab claw clipping a triangle

knipsa is a Rust polygon toolkit for boolean operations, offsets, point queries, and triangulation. It has a safe Rust API and a small C-compatible library for applications written in other languages.

The current release line is 0.2. The Rust API is still 0.x, so breaking changes remain possible before 1.0; patch releases preserve the 0.2 API.

Quick start

From crates.io:

cargo add knipsa@0.2

Projects already using geo-types can enable zero-policy conversion helpers:

cargo add knipsa@0.2 --features geo-types

The knipsa::geo_types module converts LineString and Polygon values while making ring closure explicit. It does not guess nesting across independent polygons.

Enable serde to serialize and deserialize points, rectangles, enums, options, resource limits, and structured errors. Since paths are ordinary vectors, Path64, PathD, and triangle collections then work automatically:

cargo add knipsa@0.2 --features serde

Serialized enum variants use explicit snake_case names.

Boolean operations work directly on ordinary Rust vectors:

use knipsa::{PointD, intersection_path_d};

fn main() -> Result<(), knipsa::Error> {
    let subject = vec![
        PointD::new(0.0, 0.0),
        PointD::new(10.0, 0.0),
        PointD::new(10.0, 10.0),
        PointD::new(0.0, 10.0),
    ];
    let clip = vec![
        PointD::new(5.0, 5.0),
        PointD::new(15.0, 5.0),
        PointD::new(15.0, 15.0),
        PointD::new(5.0, 15.0),
    ];

    let result = intersection_path_d(&subject, &clip)?;

    assert_eq!(result.len(), 1);
    Ok(())
}

The same example, including offsets, triangulation, and point classification, is runnable from the repository:

cargo run -p knipsa --example quickstart

Choosing the API

Each coordinate/cardinality combination has one canonical name; the 0.x API intentionally does not retain duplicate aliases. Integer helpers use the 64 suffix where a suffix is needed, while floating-point helpers use _d. The configurable Boolean entry points are boolean_op and boolean_op_d.

Need Use
Two individual rings intersection_path, union_path, difference_path, xor_path and _d variants
Ring collections with EvenOdd intersection, union, difference, xor and _d variants
Exact integer polygon booleans boolean_op with Point64
Fractional coordinates boolean_op_d with PointD
Clean self-intersections or internal boundaries simplify_paths64 or simplify_paths_d
Clip paths to an axis-aligned rectangle clip_to_rect64 or clip_to_rect_d
Remove redundant collinear vertices trim_collinear64 or trim_collinear_d
Locate a malformed path or coordinate validate_paths64_located or validate_paths_d_located
One polygon or polyline offset offset_path64 or offset_path_d
Polygon or polyline offset collections offset_paths64 or offset_paths_d
A single polygon's triangles triangulate_path64 or triangulate_path_d
Multiple rings, holes, or islands triangulate64 or triangulate_d
Untrusted triangulation input triangulate64_with_limits or triangulate_d_with_limits
Integer point-in-polygon queries point_in_polygon

Integer operations preserve integer coordinates. The floating-point boolean API accepts finite f64 values and computes intersections exactly before returning f64 coordinates. The convenience operations use the orientation-independent EvenOdd rule; use boolean_op/boolean_op_d when a different fill rule is required.

Offset options have named constructors for the common modes:

use knipsa::{EndType, JoinType, OffsetOptions, offset_path_d, offset_paths_d};

# fn example(ring: &knipsa::PathD, lines: &[knipsa::PathD]) -> Result<(), knipsa::Error> {
let expanded = offset_path_d(ring, 4.0, OffsetOptions::polygon(JoinType::Round))?;
let stroke = offset_paths_d(
    lines,
    2.0,
    OffsetOptions::polyline(JoinType::Round, EndType::Round).with_arc_tolerance(0.01),
)?;
# let _ = (expanded, stroke);
# Ok(())
# }

Closed offsets first try a certified contour forest. Simple generated rings with no boundary contact are merged by containment and integer winding. Touching, overlapping, self-crossing, oversized, or numerically ambiguous contours fall back to the exact NonZero Boolean cleanup, so callers do not need to choose a fast path or an epsilon policy.

Geometry conventions

  • Boolean and triangulation inputs are closed rings. Do not repeat the first point at the end; if it is repeated, normalization removes it.
  • Empty paths and empty path collections are valid and represent no geometry.
  • Coordinates use the ordinary Cartesian convention: positive signed area is counter-clockwise winding.
  • EvenOdd uses crossing parity. NonZero, Positive, and Negative use winding direction.
  • Offset Polygon mode handles closed rings. Joined, Butt, Square, and Round handle open polylines.
  • Triangulation returns counter-clockwise triangles and supports nested holes and islands.
  • TriangulationLimits::DEFAULT bounds path count, total vertices, and the conservative edge-pair workload before quadratic validation begins. The original entry points remain unlimited for backward compatibility.

Every fallible operation returns knipsa::Error, so callers can handle bad paths, non-finite coordinates, overflow, and topology failures without a panic. Applications that need input locations can run the _located collection validators first and receive PathValidationError with stable path and optional point indices.

C and other languages

The knipsa-ffi crate exposes the same operations through a C ABI. The 0.2 ABI is preserved across 0.2.x patch releases; pre-1.0 minor releases may break it. The public header is crates/knipsa-ffi/include/knipsa.h, and the ownership and null-pointer rules are documented in docs/ffi.md.

Outputs allocated by the FFI must be released with the matching knipsa_free_paths64 or knipsa_free_paths_d function. Input memory remains owned by the caller. Initialize output slots with KNIPSA_PATHS64_INIT or KNIPSA_PATHS_D_INIT; configure offsets with KNIPSA_OFFSET_OPTIONS_INIT. Use examples/quickstart.c as a complete C11 example.

Workspace

  • crates/knipsa — the safe Rust API and geometry engine;
  • crates/knipsa-ffi — the C-compatible library and public header;
  • crates/knipsa/examples/quickstart.rs — a runnable API tour;
  • examples/quickstart.c — a runnable C11 API tour;
  • tests/c — a C11 ABI smoke test;
  • fuzz — fuzz targets for geometry inputs;
  • docs/ — API contracts, testing notes, licensing, and benchmarks.

Development

cargo fmt --all -- --check
cargo test --workspace --all-features
cargo clippy --workspace --all-targets --all-features -- -D warnings
RUSTDOCFLAGS="-D warnings" cargo doc --workspace --all-features --no-deps
./scripts/check-c-api.sh
./scripts/coverage.sh
./scripts/fuzz-replay.sh
make conformance-integer
make conformance-offset
make conformance-triangulation
make release-check

The coverage command requires cargo-llvm-cov; deterministic fuzz replay requires cargo-fuzz and the nightly Rust toolchain.

See CHANGELOG.md for release notes, docs/migrating-0.2.md for the intentionally breaking 0.1 to 0.2 API changes, docs/release-scope-0.2.md for the 0.2 compatibility contract and known gaps, and docs/releasing.md for the crate publication procedure.

License

Licensed under either of:

  • Apache License, Version 2.0;
  • MIT License.