kika 0.3.0

Robust 2D kernel for Rust: exact predicates, Delaunay triangulation, constrained Delaunay triangulation, and simple-polygon triangulation, with adaptive/exact fallback arithmetic. No CMake, no Boost, no GMP/MPFR, WASM-ready.
Documentation

Kika

English | 日本語 | 简体中文

Kika — Robust Computational Geometry for Rust. A pure-Rust, memory-safe alternative to CGAL for developers who want robust geometric predicates without CMake, Boost, or a hard GMP/MPFR dependency.

Kika ("幾何", Japanese for "geometry") is a Rust library building toward robust 2D/3D computational geometry: exact predicates with adaptive/exact fallback arithmetic, and — in later phases — triangulation, hull, and polygon algorithms built on top of that foundation.

Status: pre-alpha (Phase 1-5 and Phase 6A-6D complete). As of 0.3.0, Kika is a robust 2D kernel with exact predicates, 2D convex hull, Delaunay triangulation, constrained Delaunay triangulation (narrow scope), and simple-polygon triangulation (narrow scope) — see Implemented today and the Maturity table below for exactly what that does and doesn't cover. No stability guarantees yet. See Roadmap for what doesn't exist yet — Kika is not a CGAL replacement, it is a robust kernel a future one could be built on.

Why not just use CGAL?

CGAL is the mature, comprehensive reference implementation for computational geometry. Kika's plan is to test its predicate layer against it as an external oracle during development (§10) — not done yet: the comparison program is unbuilt and currently environment-blocked (no CGAL/pkg-config available in this project's development environment), see docs/compatibility.md and tasks/todo.md. Today's exactness claims are verified against independent num-bigint/num-rational oracles instead (see Implemented today below), not against CGAL. Pulling CGAL into a Rust project at all means a C++ toolchain, CMake, Boost, and usually GMP/MPFR — friction that's real for cargo build-only workflows, WASM targets, and teams that want a pure-Rust dependency tree.

Kika's bet, in order:

CGAL Kika
Language C++ Pure Rust
Build CMake + Boost cargo build
Big-number dependency GMP/MPFR (typically required) Not required at runtime (dev-only, for test oracles)
Memory safety Manual Enforced by the compiler (unsafe disallowed by default, see docs/architecture.md)
WASM target Not practical wasm32-unknown-unknown, CI-checked
License GPL / commercial MIT OR Apache-2.0
Feature breadth today Very large, decades mature Deliberately small — see Implemented today

If you need mesh Booleans, NURBS, or a CAD kernel today, that's CGAL, not Kika. If you want a small, robust, panic-free predicate layer to build on in pure Rust, that's what Phase 1 of Kika is.

Implemented today

  • Point2, Point3 — finite-coordinate points (f64). Construction validates and rejects NaN/infinity; once constructed, always finite. Equality is exact coordinate equality (no tolerance) — see ADR-003.

  • Vector2, Vector3 — finite-coordinate displacement vectors, with the standard point/vector affine arithmetic (Point ± Vector -> Point, Point - Point -> Vector, vector +/-/- (negate)/* f64).

  • Segment2, Triangle2, Triangle3, Aabb2, Aabb3 — plain data types over the above (no extra validation beyond what Point2/Point3 already guarantee); zero-length segments and degenerate (collinear-vertex) triangles are valid, representable values, not rejected. Aabb2/Aabb3 give an exact, orient2d-free overlaps() fast-reject test.

  • Segment2::relation_to, Triangle2::orientation/relation_to — exact point-on-segment and point-in-triangle predicates, built entirely from orient2d. Each degenerate case (zero-length segment, collinear triangle) is handled explicitly, not assumed to fall out of the general algorithm — one case initially didn't and was caught by testing, see docs/degeneracy-policy.md. Checked against an independent exact-rational oracle in tests/differential/.

  • segment_intersection_kind / segment_intersection — robust 2D segment intersection, classification and coordinate construction deliberately kept as separate functions (§4.2): classification (None/Proper/EndpointTouch/CollinearTouch/CollinearOverlap) never divides or builds a new coordinate, with an Aabb2-based fast-reject ahead of any predicate call. Construction is exact for every case, including Proper (the one case that needs a genuinely new coordinate, correctly rounded as of Phase 5) — see Exact predicates vs. exact constructions. Checked against an independent exact-rational oracle in tests/differential/.

  • Polygon2 — a vertex ring, implicitly closed (no repeated first/last vertex). signed_area() (plain f64, a construction) and orientation() (exact — sums every edge's shoelace term via the same exact-expansion machinery the core predicates use, not a running f64 sum) are kept separate on purpose, same split as everywhere else. basic_validity() covers the cheap structural checks (vertex count, consecutive-duplicate vertices, zero area); find_self_intersection() is the separate, O(n²) check across non-adjacent edges (adjacent edges' shared vertex is correctly never reported as a self-intersection).

  • Sign, Orientation — meaningful enums returned by predicates (never a raw determinant, never an ambiguous bool).

  • orient2d — exact-sign 2D orientation predicate. Uses a fast floating-point filter with a computed error bound (never a fixed epsilon) and falls back to exact expansion-arithmetic evaluation when the filter is inconclusive. Checked against an independent exact-rational oracle in tests/differential/. See docs/numerical-model.md.

  • orient3d — exact-sign tetrahedron-orientation predicate. Same filter + exact-fallback design as orient2d. Checked against an independent exact-rational oracle in tests/differential/.

  • incircle — exact-sign point-in-circumcircle predicate. Same filter + exact-fallback design, with a narrower verified-safe coordinate-magnitude range (~1e-70..~1e70) than orient2d/ orient3d due to its higher polynomial degree — see docs/numerical-model.md. Checked against an independent exact-rational oracle in tests/differential/.

  • insphere — exact-sign point-in-circumsphere predicate, the 3D analog of incircle. Same filter + exact-fallback design, with an even narrower verified-safe coordinate-magnitude range (~1e-30..~1e30) than incircle — see docs/numerical-model.md. Checked against an independent exact-rational oracle in tests/differential/.

  • convex_hull2 / HullBoundaryPoints — 2D convex hull via Andrew's monotone chain. ExtremesOnly (default) keeps only strict corners; KeepAllOnBoundary also keeps boundary points collinear with their neighbors. Counterclockwise output, starting at the lexicographically smallest input point, independent of input order; duplicate input points are collapsed first. Fully exact — every returned vertex is copied from an original input Point2, since the algorithm is built entirely from orient2d with no interpolation or division anywhere. Degenerate inputs (0/1/2 points, all-collinear) are handled explicitly, not left to the general algorithm — see docs/degeneracy-policy.md.

  • delaunay2 / Triangulation2 — 2D Delaunay triangulation via Bowyer-Watson incremental insertion. Fully exact, like convex_hull2: "outside the triangulation" is represented by a single symbolic ghost vertex (no coordinate), not a synthetic bounding triangle, so there is no scale-dependent tradeoff to work around — verified down to a perpendicular cluster spread of 1e-200 relative to a span of 10.0. Cocircular points are a real tie among multiple valid triangulations, not a single "correct" answer; the deterministic tie-break rule is documented in docs/degeneracy-policy.md alongside every other degenerate case (collinear boundary points, points exactly on an existing edge).

  • Triangulation2's adjacency structure — VertexId/EdgeId/FaceId and vertices/edges/faces/edge_vertices/adjacent_faces/ face_vertices/neighboring_faces/boundary_edges, a static, post-construction snapshot of the indexed-triangle-adjacency structure (no half-edge/quad-edge generality, per ADR-006's comparison). triangles() keeps its original coordinate-only contract unchanged; the new methods are purely additive.

  • constrained_delaunay2 / ConstrainedTriangulation2 — 2D constrained Delaunay triangulation, deliberately narrow scope (Phase 6C): only non-crossing constraint edges between existing input vertices, no automatic intersection/Steiner-point generation, no refinement. Built entirely by flipping existing Delaunay edges via the crate's own orient2d/incircle/segment_intersection_kind predicates — ADR-004's Phase 6 re-evaluation predicted CDT needs no new construction, and the implementation confirms it: not one new coordinate is ever built. Constraint recovery and Delaunay restoration are each bounded (never an unbounded loop); CdtError reports crossing/collinear constraints, algorithm exhaustion, and a degenerate point set (fewer than 3 points, or all collinear) as typed errors, never a panic.

  • triangulate_polygon — simple-polygon triangulation (Phase 6D), built on Phase 6C's CDT: constrain every polygon edge, then discard the concave-pocket faces outside the polygon (for a non-convex input) via a purely topological flood fill from one interior seed face — never a constructed point such as a centroid. No holes, no Steiner points (every output vertex is one of the polygon's own), self-intersecting input rejected as a typed PolygonTriangulationError, both CCW and CW input accepted, deterministic. See docs/degeneracy-policy.md for the full scope table, including a caveat for checking the result with Triangulation2::validate_topology() (its Euler-characteristic check assumes full convex-hull coverage, which a non-convex polygon's triangulation deliberately doesn't have).

All four predicates complete v0.1's robust-predicate scope; the primitives, intersections, polygon, convex hull, and Delaunay triangulation above complete Phases 2 through 4. segment_intersection's Proper-crossing point construction (below) completes Phase 5, and the adjacency structure, constrained Delaunay triangulation, and simple-polygon triangulation above complete Phase 6A-6D. Everything past this point (polygon Boolean, exact Voronoi) is later — see Roadmap.

  • predicates::line_intersection (used internally by segment_intersection's Proper case) — the first exact/certified construction in the crate, per ADR-004. Returns the correctly-rounded (round-to-nearest-even on exact ties) f64 nearest to the true intersection coordinate, not an approximation — the same guarantee IEEE-754 makes for a single arithmetic operation, extended to a whole geometric construction. Point2 stays a plain f64 pair; no new public type, no new dependency. Verified against an independent BigRational "is this the correctly-rounded nearest f64" oracle across magnitude scales, mixed-magnitude inputs, and an empirical floor sweep — see docs/numerical-model.md.

Exact predicates vs. exact constructions

Kika's predicates (orient2d etc.) guarantee a mathematically correct sign. Guaranteeing that a generated coordinate is exact is a separate problem ("construction") — as of Phase 5, one case is solved: segment_intersection's Proper-crossing point is now a correctly-rounded construction (predicates::line_intersection, ADR-004), unlike the naive f64 interpolation it used to be. It joins the other cases that function can return (EndpointTouch/CollinearTouch/CollinearOverlap), which were already exact by reusing an original input coordinate directly. See docs/architecture.md §4.2 and ADR-004. Do not assume constructions implemented in later phases (Phase 6: constrained Delaunay, polygon Boolean) carry the same exactness guarantee until their own docs say so.

Degenerate cases

Collinear/coplanar/cocircular/cospherical points, duplicate points, signed zero, and subnormal coordinates are handled explicitly and tested, not treated as "rare enough to ignore." See docs/degeneracy-policy.md.

Minimal example

use kika::{Point2, orient2d, Orientation};

let a = Point2::new(0.0, 0.0).unwrap();
let b = Point2::new(1.0, 0.0).unwrap();
let c = Point2::new(0.0, 1.0).unwrap();

assert_eq!(orient2d(a, b, c), Orientation::CounterClockwise);

Constrained Delaunay — every constraint edge is guaranteed present in the result, even where flipping it away would otherwise be the Delaunay choice (this exact snippet is doctested — cargo test --doc — as constrained_delaunay2's own doc example):

use kika::{Point2, constrained_delaunay2};

let pts = [
    Point2::new(0.0, 0.0).unwrap(),
    Point2::new(4.0, 0.0).unwrap(),
    Point2::new(4.0, 4.0).unwrap(),
    Point2::new(0.0, 4.0).unwrap(),
];
let constraints = [(0, 2)]; // one diagonal of the square
let cdt = constrained_delaunay2(&pts, &constraints).unwrap();

let constrained_edge_count = cdt
    .triangulation()
    .edges()
    .filter(|&e| cdt.is_constrained(e))
    .count();
assert_eq!(constrained_edge_count, constraints.len());

Simple-polygon triangulation — no holes, no Steiner points, built on the constrained Delaunay above (also doctested, as triangulate_polygon's own doc example):

use kika::{Point2, Polygon2, triangulate_polygon};

let square = Polygon2::new(vec![
    Point2::new(0.0, 0.0).unwrap(),
    Point2::new(4.0, 0.0).unwrap(),
    Point2::new(4.0, 4.0).unwrap(),
    Point2::new(0.0, 4.0).unwrap(),
]);
let t = triangulate_polygon(&square).unwrap();

// A simple polygon triangulated with only its own vertices always has
// exactly `polygon.len() - 2` triangles.
assert_eq!(t.len(), square.len() - 2);

More, runnable via cargo run --example <name>, in examples/:

WASM

The predicate core has no OS or platform-specific code and builds for wasm32-unknown-unknown; this is checked in CI. No WASM-specific bindings (wasm-bindgen etc.) exist yet.

Difference from CGAL

Kika does not link CGAL and shares no source with it. CGAL is planned to be used only as an external, separate differential-test oracle during development (§10 of the project's development instructions) — never as a runtime or build dependency of the kika crate — but that comparison program does not exist yet; see Why not just use CGAL? above.

Stability

Pre-1.0, no semver guarantees. The public Kernel trait design described in some computational-geometry libraries (CGAL included) is explicitly not being finalized yet — see ADR-004. As of 0.3.0, the public Result-style error enums (KikaError, CdtError, PolygonTriangulationError) are #[non_exhaustive], so a future variant addition won't break a downstream match that already has a wildcard arm — see CHANGELOG.md.

Maturity

Feature Status
Predicates (orient2d, orient3d, incircle, insphere) Stable enough for evaluation — filter + exact fallback, checked against independent oracles
Segment intersection Implemented — classification exact, Proper construction correctly rounded (ADR-004)
Convex hull Implemented — fully exact
Delaunay triangulation Implemented — fully exact, no synthetic coordinates
Triangulation adjacency (vertex/edge/face queries) Implemented — VertexId/EdgeId/FaceId, neighbor/boundary queries, internal topology validator (ADR-006)
Constrained Delaunay Implemented — narrow scope: non-crossing constraints between existing vertices only, no Steiner points (Phase 6C)
Simple polygon triangulation Implemented — narrow scope: no holes, no Steiner points, self-intersecting input rejected (Phase 6D)
Polygon Boolean Not implemented — exactness model still open, see ADR-004
3D mesh operations Not implemented

License

Licensed under either of

at your option.

Roadmap

Phase 1 (robust predicates), Phase 2 (2D primitives and intersections), Phase 3 (2D convex hull), Phase 4 (2D Delaunay triangulation), Phase 5 (certified/exact constructions — an exact Proper segment-intersection point), and Phase 6A-6D (triangulation adjacency, narrow-scope constrained Delaunay, narrow-scope simple-polygon triangulation) are complete. Not yet implemented: polygon/mesh Boolean; exact Voronoi construction; vertex deletion; Delaunay refinement; mesh repair; surface reconstruction; point-cloud processing. See tasks/todo.md for the phased backlog and docs/release-checklist.md for what's verified vs. still needed before an actual crates.io/GitHub release (neither has happened yet).