Skip to main content

Crate kika

Crate kika 

Source
Expand description

Kika — a robust 2D kernel for Rust: exact predicates, Delaunay triangulation, constrained Delaunay triangulation, and simple-polygon triangulation.

Pre-1.0, no stability guarantees yet; see the repository README and docs/ for exact scope (each triangulation feature is narrow-scope — see the Maturity table) and status.

Re-exports§

pub use triangulation::CdtError;
pub use triangulation::ConstrainedTriangulation2;
pub use triangulation::EdgeId;
pub use triangulation::FaceId;
pub use triangulation::PointLocation;
pub use triangulation::PolygonTriangulationError;
pub use triangulation::Triangulation2;
pub use triangulation::VertexId;
pub use triangulation::Voronoi2;
pub use triangulation::VoronoiCellId;
pub use triangulation::VoronoiEdge;
pub use triangulation::VoronoiEdgeGeometry;
pub use triangulation::VoronoiEdgeId;
pub use triangulation::VoronoiEdgeKind;
pub use triangulation::VoronoiGeometryError;
pub use triangulation::VoronoiVertexId;
pub use triangulation::constrained_delaunay2;
pub use triangulation::delaunay2;
pub use triangulation::triangulate_polygon;
pub use triangulation::triangulate_polygon_with_holes;
pub use triangulation::voronoi2;

Structs§

Aabb2
An axis-aligned bounding box in 2D: min.x() <= max.x() and min.y() <= max.y(), enforced by construction (there is no path to build an Aabb2 with an inverted or otherwise invalid extent).
Aabb3
An axis-aligned bounding box in 3D. See super::Aabb2’s doc comment; same design, one more axis.
ConstrainedTriangulation2
A 2D constrained Delaunay triangulation: a Triangulation2 plus a marked set of edges that are guaranteed present and were never flipped away, even where doing so would otherwise be locally Delaunay — see constrained_delaunay2.
EdgeId
An opaque handle to one of a super::Triangulation2’s undirected edges. See VertexId’s doc comment for the cross-triangulation caveat.
FaceId
An opaque handle to one of a super::Triangulation2’s triangular faces. See VertexId’s doc comment for the cross-triangulation caveat.
Point2
A 2D point with finite f64 coordinates.
Point3
A 3D point with finite f64 coordinates.
Polygon2
A 2D polygon ring: vertices[i] to vertices[(i+1) % n], including the wraparound edge back to vertices[0] — implicitly closed (unlike e.g. GeoJSON, the first vertex is not repeated at the end).
PolygonSelfIntersection
A found self-intersection, from Polygon2::find_self_intersection: the two (non-adjacent) edge indices and the kind of intersection between them.
Segment2
A 2D line segment between two points.
Triangle2
A 2D triangle with vertices a, b, c, in the order given (no implied winding — a degenerate, collinear-vertex triangle is a valid, representable Triangle2, not rejected).
Triangle3
A 3D triangle with vertices a, b, c, in the order given.
Triangulation2
A 2D Delaunay triangulation: a set of non-overlapping, counterclockwise-wound Triangle2s whose union is the input’s convex hull, with no input point strictly inside any triangle’s circumcircle, plus the adjacency between them (§6B, ADR-006).
Vector2
A 2D displacement with finite f64 components.
Vector3
A 3D displacement with finite f64 components. See super::Vector2’s doc comment for the arithmetic-doesn’t-re-validate convention.
VertexId
An opaque handle to one of a super::Triangulation2’s vertices.
Voronoi2
A 2D Voronoi diagram: the dual of a Triangulation2, owned by value (no lifetime parameter), matching super::ConstrainedTriangulation2’s precedent.
VoronoiCellId
A Voronoi cell, identified with the VertexId of the Delaunay site it surrounds – a true bijection, so no separate cell table is kept.
VoronoiEdge
One edge of a Voronoi diagram: the two cells it separates, its shape (bounded segment or unbounded ray), and the Delaunay edge it is dual to.
VoronoiEdgeId
A Voronoi edge: the dual of a Delaunay edge whose two sides fall in different face groups (an excluded same-group Delaunay edge is a spurious artifact of the input triangulation’s tie-break, not a real Voronoi edge – see voronoi2).
VoronoiVertexId
A Voronoi vertex: the dual of one connected group of Delaunay faces merged by cocircularity (§“Cocircular tie-break normalization”, ADR-007). Usually one face, but every face in a cocircular cluster (e.g. all faces of a triangulated square) shares a single VoronoiVertexId, since they share a single true circumcenter.

Enums§

CdtError
Why constrained_delaunay2 rejected an input or failed to build a result.
HullBoundaryPoints
Whether convex_hull2 keeps points that lie exactly on the hull boundary but are not themselves extreme (i.e. collinear with their two neighbors on the boundary).
KikaError
Error type for fallible Kika constructors.
Orientation
The orientation of an ordered sequence of 2D points.
PointLocation
Where a query point falls relative to a Triangulation2.
PointPolygonRelation
Where a point lies relative to a Polygon2 ring, per Polygon2::relation_to.
PointSegmentRelation
Where a point lies relative to a Segment2, per Segment2::relation_to.
PointTriangleRelation
Where a point lies relative to a Triangle2, per Triangle2::relation_to.
PolygonBasicValidity
The outcome of Polygon2::basic_validity — the cheap structural checks (§9 Phase 2 “polygon基本validity検査”), not the separate, O(n²) Polygon2::find_self_intersection check.
PolygonTriangulationError
Why triangulate_polygon rejected an input or failed to build a result.
SegmentIntersection2
The constructed geometry of a segment intersection (§4.2/§8’s construction side, separate from SegmentIntersectionKind’s classification).
SegmentIntersectionKind
The kind of intersection between two 2D segments, per AGENTS.md §9 Phase 2’s required classification. This is the predicate side (§4.2): computing it never constructs new coordinates or divides — see segment_intersection for the separate construction side.
Sign
The sign of an exact geometric quantity (e.g. a determinant).
VoronoiEdgeGeometry
The actual geometry of a VoronoiEdge (ADR-009): a bounded segment between two Voronoi vertex coordinates, or an unbounded ray from one.
VoronoiEdgeKind
Whether a VoronoiEdge is a finite segment between two Voronoi vertices, or an infinite ray from one Voronoi vertex out to infinity.
VoronoiGeometryError
Why Voronoi2::vertex_point/Voronoi2::edge_geometry couldn’t produce a coordinate (ADR-009).

Functions§

constrained_delaunay2
Builds the constrained Delaunay triangulation of points with the given constraints (pairs of indices into points), or a typed error explaining why it couldn’t.
convex_hull2
The 2D convex hull of points, via Andrew’s monotone chain algorithm.
delaunay2
The 2D Delaunay triangulation of points, via Bowyer-Watson incremental insertion with a symbolic “point at infinity” standing in for a synthetic bounding triangle.
incircle
The sign of det [adx ady adz; bdx bdy bdz; cdx cdy cdz] where Xdx = X.x()-d.x(), Xdy = X.y()-d.y(), Xdz = Xdx^2+Xdy^2 — the standard “lift to the paraboloid” incircle determinant.
insphere
The sign of the 4x4 “lift to the 4D paraboloid” determinant det [adx ady adz adw; bdx bdy bdz bdw; cdx cdy cdz cdw; ddx ddy ddz ddw] where Xdx = X.x()-e.x() etc. and Xdw = Xdx^2+Xdy^2+Xdz^2.
orient2d
The orientation of the ordered triple (a, b, c): whether c lies to the left of, to the right of, or on the directed line through a and b — equivalently, the sign of twice the signed area of triangle abc.
orient3d
The sign of det [a-d; b-d; c-d] (the determinant with rows a-d, b-d, c-d), proportional to the signed volume of the tetrahedron (a, b, c, d). Sign::Zero means the four points are coplanar.
segment_intersection
Constructs the intersection geometry of s1 and s2. See SegmentIntersection2’s doc comment for exactness caveats — only the Proper case computes a new coordinate (and divides); every other case reuses an original input point exactly.
segment_intersection_kind
Classifies the intersection of s1 and s2. Never constructs a new coordinate or divides — see the type’s doc comment.
triangulate_polygon
Triangulates a simple polygon (no holes, no self-intersections) using only its own input vertices — no Steiner points (see the module doc comment for full scope). Accepts both CCW and CW input.
triangulate_polygon_with_holes
Triangulates a simple polygon with holes: outer’s interior, minus each hole’s interior. No Steiner points (every output vertex is one of outer’s or a hole’s own vertices) — see the module doc comment. Accepts any mix of CW/CCW winding for outer and each hole independently; orientation is normalized internally.
voronoi2
Builds the Voronoi2 topology dual to delaunay.