iTriangle

iTriangle is a high-performance 2D polygon triangulation library for Rust. It turns real-world polygon input into triangle meshes, including shapes with holes, self-intersections, and mixed winding. The public API accepts f32/f64 floating-point data and i16/i32/i64 integer data, while the triangulation pipeline runs through a deterministic integer core for stable, reproducible output.

For detailed performance benchmarks, check out thePerformance Comparison

Table of Contents

• Why iTriangle?
• Features
• Data Types and Solvers
• Architecture Overview
• Quick Start
• Documentation
• Examples
• Integer API
• Performance
• Gallery
• Contributing
• License

Why iTriangle?

• Robust on complex input: supports holes, self-intersections, degenerate edges, and mixed winding.
• Deterministic core: geometry is processed with integer math, avoiding many floating-point corner cases.
• Flexible numeric model: use f32/f64 input or work directly with i16/i32/i64 integer coordinates.
• Mesh-ready outputs: triangles, Delaunay meshes, convex decomposition, tessellation, and centroid nets.

Features

• Sweep-line Triangulation - Fast and simple triangulation of polygons with or without holes.
• Delaunay Triangulation - Efficient and robust implementation for generating Delaunay triangulations.
• Self-Intersection Handling – Fully supports self-intersecting polygons with automatic resolution.
• Adaptive Tessellation - Refine Delaunay triangles using circumcenters for better shape quality.
• Convex Decomposition - Convert triangulation into convex polygons.
• Centroidal Polygon Net: Build per-vertex dual polygons using triangle centers and edge midpoints.
• Steiner Points: Add custom inner points to influence triangulation.
• GPU-Friendly Layout: Triangles and vertices are naturally ordered by X due to the sweep-line algorithm, improving cache locality for rendering.

Data Types and Solvers

iTriangle is designed around a deterministic integer core:

• Floating-point APIs accept f32 and f64 compatible point types, then map them into integer coordinates before triangulation.
• Integer APIs work directly with i16, i32, or i64 coordinates when your geometry is already quantized.
• i32 is the default integer coordinate type for floating-point input.
• i64 is useful for larger coordinate ranges or finer fixed precision.
• i16 can be useful for compact, bounded datasets where memory and cache behavior matter.

Architecture Overview

Quick Start

Add to your Cargo.toml:

[dependencies]
i_triangle = "0.45"

Minimal example:

use i_triangle::float::triangulatable::Triangulatable;let contour = vec![[0.0,0.0],[10.0,0.0],[10.0,10.0],[0.0,10.0],];let triangulation = vec![contour].triangulate().to_triangulation::<u16>();println!("triangles: {}", triangulation.indices.len() / 3);

By default, float input is converted to the robust integer core using i32 coordinates. If your geometry needs a different integer precision, choose it explicitly:

use i_triangle::float::triangulatable::Triangulatable;use i_triangle::float::triangulator::Triangulator;let shape = vec![vec![[0.0,0.0],[10.0,0.0],[10.0,10.0],[0.0,10.0],]];// One-shot triangulation with i64 integer coordinates.let mesh = shape.triangulate_as::<i64>().to_triangulation::<u32>();// Reusable triangulator: first generic is index type, second is coordinate type.letmut triangulator = Triangulator::<u32,i64>::default();let mesh = triangulator.triangulate(&shape);

Documentation

• Docs.rs
• Delaunay
• Demos

Examples

Single Shape Triangulation

use i_triangle::float::triangulatable::Triangulatable;use i_triangle::float::triangulation::Triangulation;let shape = vec![
vec![// body[0.0,20.0],// 0[-10.0,8.0],// 1[-7.0,6.0],// 2[-6.0,2.0],// 3[-8.0, -2.0],// 4[-13.0, -4.0],// 5[-16.0, -3.0],// 6[-18.0,0.0],// 7[-25.0, -7.0],// 8[-14.0, -15.0],// 9[0.0, -18.0],// 10[14.0, -15.0],// 11[26.0, -7.0],// 12[17.0,1.0],// 13[13.0, -1.0],// 14[9.0,1.0],// 15[7.0,6.0],// 16[8.0,10.0],// 17],
vec![// hole[2.0,0.0],// 0[5.0, -2.0],// 1[7.0, -5.0],// 2[5.0, -9.0],// 3[2.0, -11.0],// 4[-2.0, -9.0],// 5[-4.0, -5.0],// 6[-2.0, -2.0],// 7],];let triangulation = shape.triangulate().to_triangulation::<u16>();println!("points: {:?}", triangulation.points);println!("indices: {:?}", triangulation.indices);let delaunay_triangulation:Triangulation<[f64;2],u16> =
shape.triangulate().into_delaunay().to_triangulation();println!("points: {:?}", delaunay_triangulation.points);println!("indices: {:?}", delaunay_triangulation.indices);let convex_polygons = shape.triangulate().into_delaunay().to_convex_polygons();println!("convex polygons: {:?}", convex_polygons);let tessellation:Triangulation<[f64;2],u16> = shape
.triangulate().into_delaunay().refine_with_circumcenters_by_obtuse_angle(0.0).to_triangulation();println!("points: {:?}", tessellation.points);println!("indices: {:?}", tessellation.indices);let centroids = shape
.triangulate().into_delaunay().refine_with_circumcenters_by_obtuse_angle(0.0).to_centroid_net(0.0);println!("centroids: {:?}", centroids);

💡 Output: Triangle indices and vertices, where all triangles oriented in a counter-clockwise direction.

Triangulating Multiple Shapes Efficiently

If you need to triangulate many shapes, it is more efficient to use Triangulator.

use i_triangle::float::triangulation::Triangulation;use i_triangle::float::triangulator::Triangulator;let contours = vec![
vec![[0.0,0.0],[4.0,0.0],[4.0,4.0],[0.0,4.0]],
vec![[5.0,0.0],[9.0,0.0],[9.0,4.0],[5.0,4.0]],];// Uses u32 triangle indices and the default i32 integer coordinate solver.letmut triangulator = Triangulator::<u32>::default();// Enable Delaunay refinement
triangulator.delaunay(true);// Use fast Earcut solver for contours with ≤ 64 points
triangulator.earcut(true);letmut triangulation = Triangulation::with_capacity(100);for contour in contours.iter(){// Triangulate using self-intersection resolver
triangulator.triangulate_into(contour,&mut triangulation);println!("points: {:?}", triangulation.points);println!("indices: {:?}", triangulation.indices);}

Integer API

The integer API is useful when your coordinates are already quantized or when you want direct control over the robust integer core. It avoids float-to-int adapter setup and returns integer points unchanged.

Use IntPoint with IntContour, IntShape, or IntShapes-compatible containers:

use i_triangle::int::triangulatable::IntTriangulatable;use i_triangle::i_overlay::i_float::int::point::IntPoint;let contour = vec![IntPoint::new(0,0),IntPoint::new(10,0),IntPoint::new(10,10),IntPoint::new(0,10),];let triangulation = contour.triangulate().into_triangulation::<u16>();assert_eq!(triangulation.points.len(),4);assert_eq!(triangulation.indices.len(),6);

For repeated triangulation, use IntTriangulator and reuse its internal buffers:

use i_triangle::int::triangulation::IntTriangulation;use i_triangle::int::triangulator::IntTriangulator;use i_triangle::i_overlay::i_float::int::point::IntPoint;let contours = vec![
vec![IntPoint::new(0,0),IntPoint::new(10,0),IntPoint::new(10,10),IntPoint::new(0,10),],
vec![IntPoint::new(20,0),IntPoint::new(30,0),IntPoint::new(30,10),IntPoint::new(20,10),],];letmut triangulator = IntTriangulator::<i32,u32>::default();letmut output = IntTriangulation::<i32,u32>::default();for contour in&contours {
triangulator.triangulate_contour_into(contour.clone(),&mut output);assert!(!output.indices.is_empty());}

If your integer contours are already valid and correctly oriented, the unchecked API skips validation:

use i_triangle::int::unchecked::IntUncheckedTriangulatable;use i_triangle::i_overlay::i_float::int::point::IntPoint;let contour = vec![IntPoint::new(0,0),IntPoint::new(10,0),IntPoint::new(10,10),IntPoint::new(0,10),];let triangulation = contour.uncheck_triangulate().into_triangulation::<u16>();assert_eq!(triangulation.indices.len(),6);

Performance

Benchmarks and interactive demos are available here:

• Performance Comparison
• Triangulation Demo
• Tessellation Demo

Gallery

Delaunay	Convex Polygons	Steiner Points

Tessellation	Centroid Net

Contributing

See CONTRIBUTING.md for development setup, tests, and PR guidelines.

License

Licensed under either of:

• MIT license (LICENSE-MIT)
• Apache License, Version 2.0 (LICENSE-APACHE)