knipsa

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:
Projects already using geo-types can enable zero-policy conversion helpers:
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:
Serialized enum variants use explicit snake_case names.
Boolean operations work directly on ordinary Rust vectors:
use ;
The same example, including offsets, triangulation, and point classification, is runnable from the repository:
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 ;
#
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.
EvenOdduses crossing parity.NonZero,Positive, andNegativeuse winding direction.- Offset
Polygonmode handles closed rings.Joined,Butt,Square, andRoundhandle open polylines. - Triangulation returns counter-clockwise triangles and supports nested holes and islands.
TriangulationLimits::DEFAULTbounds 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
RUSTDOCFLAGS="-D warnings"
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.