iTriangle

iTriangle is a high-performance 2D polygon triangulation library for Rust. It solves robust triangulation for real-world, messy input (holes, self-intersections, mixed winding) and is built for GIS/CAD, simulation, and rendering pipelines that need deterministic results.

For detailed performance benchmarks, check out the Performance Comparison

Why iTriangle?
Features
Architecture Overview
Quick Start
Documentation
Examples
Performance
Gallery
Contributing
License

Why iTriangle?

Robust on complex input: supports holes and self-intersections with automatic resolution.
Deterministic and stable: integer-based core avoids floating-point corner cases.
High-performance: optimized sweep-line triangulation with cache-friendly outputs.
Flexible outputs: Delaunay, 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.

Architecture Overview

flowchart TD
    A[Input contours] --> B[Normalize and fix self-intersections]
    B --> C[Sweep-line triangulation]
    C --> D[Raw triangulation]
    D -->|Delaunay| E[Delaunay triangulation]
    D --> I[Triangles and indices]
    E -->|Tessellation| F[Adaptive refinement]
    F --> E
    E --> G[Convex decomposition]
    E --> H[Centroid net]
    E --> I

Quick Start

Add to your Cargo.toml:

[dependencies]
i_triangle = "0.36"

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);

Documentation

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.

let contours = random_contours(100);

let mut triangulator = Triangulator::<u32>::default();

// Enable Delaunay refinement
triangulator.delaunay(true);

// Use fast Earcut solver for contours with ≤ 64 points
triangulator.earcut(true);

let mut 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);
}

Performance

Benchmarks and interactive demos are available here:

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)

i_triangle 0.39.1