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()andmin.y() <= max.y(), enforced by construction (there is no path to build anAabb2with 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. - Constrained
Triangulation2 - A 2D constrained Delaunay triangulation: a
Triangulation2plus a marked set of edges that are guaranteed present and were never flipped away, even where doing so would otherwise be locally Delaunay — seeconstrained_delaunay2. - EdgeId
- An opaque handle to one of a
super::Triangulation2’s undirected edges. SeeVertexId’s doc comment for the cross-triangulation caveat. - FaceId
- An opaque handle to one of a
super::Triangulation2’s triangular faces. SeeVertexId’s doc comment for the cross-triangulation caveat. - Point2
- A 2D point with finite
f64coordinates. - Point3
- A 3D point with finite
f64coordinates. - Polygon2
- A 2D polygon ring:
vertices[i]tovertices[(i+1) % n], including the wraparound edge back tovertices[0]— implicitly closed (unlike e.g. GeoJSON, the first vertex is not repeated at the end). - Polygon
Self Intersection - 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, representableTriangle2, 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
f64components. - Vector3
- A 3D displacement with finite
f64components. Seesuper::Vector2’s doc comment for the arithmetic-doesn’t-re-validate convention. - Vertex
Id - 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), matchingsuper::ConstrainedTriangulation2’s precedent. - Voronoi
Cell Id - A Voronoi cell, identified with the
VertexIdof the Delaunay site it surrounds – a true bijection, so no separate cell table is kept. - Voronoi
Edge - 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.
- Voronoi
Edge Id - 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). - Voronoi
Vertex Id - 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_delaunay2rejected an input or failed to build a result. - Hull
Boundary Points - Whether
convex_hull2keeps points that lie exactly on the hull boundary but are not themselves extreme (i.e. collinear with their two neighbors on the boundary). - Kika
Error - Error type for fallible Kika constructors.
- Orientation
- The orientation of an ordered sequence of 2D points.
- Point
Location - Where a query point falls relative to a
Triangulation2. - Point
Polygon Relation - Where a point lies relative to a
Polygon2ring, perPolygon2::relation_to. - Point
Segment Relation - Where a point lies relative to a
Segment2, perSegment2::relation_to. - Point
Triangle Relation - Where a point lies relative to a
Triangle2, perTriangle2::relation_to. - Polygon
Basic Validity - The outcome of
Polygon2::basic_validity— the cheap structural checks (§9 Phase 2 “polygon基本validity検査”), not the separate, O(n²)Polygon2::find_self_intersectioncheck. - Polygon
Triangulation Error - Why
triangulate_polygonrejected an input or failed to build a result. - Segment
Intersection2 - The constructed geometry of a segment intersection (§4.2/§8’s
construction side, separate from
SegmentIntersectionKind’s classification). - Segment
Intersection Kind - 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_intersectionfor the separate construction side. - Sign
- The sign of an exact geometric quantity (e.g. a determinant).
- Voronoi
Edge Geometry - The actual geometry of a
VoronoiEdge(ADR-009): a bounded segment between two Voronoi vertex coordinates, or an unbounded ray from one. - Voronoi
Edge Kind - Whether a
VoronoiEdgeis a finite segment between two Voronoi vertices, or an infinite ray from one Voronoi vertex out to infinity. - Voronoi
Geometry Error - Why
Voronoi2::vertex_point/Voronoi2::edge_geometrycouldn’t produce a coordinate (ADR-009).
Functions§
- constrained_
delaunay2 - Builds the constrained Delaunay triangulation of
pointswith the givenconstraints(pairs of indices intopoints), 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]whereXdx = 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]whereXdx = X.x()-e.x()etc. andXdw = Xdx^2+Xdy^2+Xdz^2. - orient2d
- The orientation of the ordered triple
(a, b, c): whetherclies to the left of, to the right of, or on the directed line throughaandb— equivalently, the sign of twice the signed area of triangleabc. - orient3d
- The sign of
det [a-d; b-d; c-d](the determinant with rowsa-d,b-d,c-d), proportional to the signed volume of the tetrahedron(a, b, c, d).Sign::Zeromeans the four points are coplanar. - segment_
intersection - Constructs the intersection geometry of
s1ands2. SeeSegmentIntersection2’s doc comment for exactness caveats — only thePropercase computes a new coordinate (and divides); every other case reuses an original input point exactly. - segment_
intersection_ kind - Classifies the intersection of
s1ands2. 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 ofouter’s or a hole’s own vertices) — see the module doc comment. Accepts any mix of CW/CCW winding forouterand each hole independently; orientation is normalized internally. - voronoi2
- Builds the
Voronoi2topology dual todelaunay.