knipsa 0.2.0

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

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

Every fallible operation returns knipsa::Error, so callers can handle bad paths, non-finite coordinates, overflow, and topology failures without a panic.

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.