Kika
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 whatPoint2/Point3already guarantee); zero-length segments and degenerate (collinear-vertex) triangles are valid, representable values, not rejected.Aabb2/Aabb3give an exact,orient2d-freeoverlaps()fast-reject test. -
Segment2::relation_to,Triangle2::orientation/relation_to— exact point-on-segment and point-in-triangle predicates, built entirely fromorient2d. 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, seedocs/degeneracy-policy.md. Checked against an independent exact-rational oracle intests/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 anAabb2-based fast-reject ahead of any predicate call. Construction is exact for every case, includingProper(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 intests/differential/. -
Polygon2— a vertex ring, implicitly closed (no repeated first/last vertex).signed_area()(plainf64, a construction) andorientation()(exact — sums every edge's shoelace term via the same exact-expansion machinery the core predicates use, not a runningf64sum) 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 ambiguousbool). -
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 intests/differential/. Seedocs/numerical-model.md. -
orient3d— exact-sign tetrahedron-orientation predicate. Same filter + exact-fallback design asorient2d. Checked against an independent exact-rational oracle intests/differential/. -
incircle— exact-sign point-in-circumcircle predicate. Same filter + exact-fallback design, with a narrower verified-safe coordinate-magnitude range (~1e-70..~1e70) thanorient2d/orient3ddue to its higher polynomial degree — seedocs/numerical-model.md. Checked against an independent exact-rational oracle intests/differential/. -
insphere— exact-sign point-in-circumsphere predicate, the 3D analog ofincircle. Same filter + exact-fallback design, with an even narrower verified-safe coordinate-magnitude range (~1e-30..~1e30) thanincircle— seedocs/numerical-model.md. Checked against an independent exact-rational oracle intests/differential/. -
convex_hull2/HullBoundaryPoints— 2D convex hull via Andrew's monotone chain.ExtremesOnly(default) keeps only strict corners;KeepAllOnBoundaryalso 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 inputPoint2, since the algorithm is built entirely fromorient2dwith no interpolation or division anywhere. Degenerate inputs (0/1/2 points, all-collinear) are handled explicitly, not left to the general algorithm — seedocs/degeneracy-policy.md. -
delaunay2/Triangulation2— 2D Delaunay triangulation via Bowyer-Watson incremental insertion. Fully exact, likeconvex_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 of1e-200relative to a span of10.0. Cocircular points are a real tie among multiple valid triangulations, not a single "correct" answer; the deterministic tie-break rule is documented indocs/degeneracy-policy.mdalongside every other degenerate case (collinear boundary points, points exactly on an existing edge). -
Triangulation2's adjacency structure —VertexId/EdgeId/FaceIdandvertices/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 ownorient2d/incircle/segment_intersection_kindpredicates — 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);CdtErrorreports 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 typedPolygonTriangulationError, both CCW and CW input accepted, deterministic. Seedocs/degeneracy-policy.mdfor the full scope table, including a caveat for checking the result withTriangulation2::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 bysegment_intersection'sPropercase) — the first exact/certified construction in the crate, per ADR-004. Returns the correctly-rounded (round-to-nearest-even on exact ties)f64nearest 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.Point2stays a plainf64pair; no new public type, no new dependency. Verified against an independentBigRational"is this the correctly-rounded nearestf64" oracle across magnitude scales, mixed-magnitude inputs, and an empirical floor sweep — seedocs/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 ;
let a = new.unwrap;
let b = new.unwrap;
let c = new.unwrap;
assert_eq!;
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 ;
let pts = ;
let constraints = ; // one diagonal of the square
let cdt = constrained_delaunay2.unwrap;
let constrained_edge_count = cdt
.triangulation
.edges
.filter
.count;
assert_eq!;
Simple-polygon triangulation — no holes, no Steiner points, built on the
constrained Delaunay above (also doctested, as
triangulate_polygon's own doc example):
use ;
let square = new;
let t = triangulate_polygon.unwrap;
// A simple polygon triangulated with only its own vertices always has
// exactly `polygon.len() - 2` triangles.
assert_eq!;
More, runnable via cargo run --example <name>, in examples/:
orient2d— the basic turn predicatesegment_intersection— classify and construct a segment crossingconvex_hull—ExtremesOnlyvsKeepAllOnBoundarydelaunay— 2D Delaunay triangulationpolygon_validity—basic_validityandfind_self_intersectionconstrained_delaunay— forcing a specific (possibly non-Delaunay) edge to survivepolygon_triangulation— a non-convex polygon, with triangle-count/CCW/area checks
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
- MIT license (LICENSE-MIT)
- Apache License, Version 2.0 (LICENSE-APACHE)
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).