34 releases (breaking)
0.26.0 | Sep 21, 2024 |
---|---|
0.25.0 | Jul 13, 2024 |
0.19.1 | Mar 31, 2024 |
0.5.0 | Dec 23, 2023 |
0.2.0 | Nov 16, 2023 |
#516 in Algorithms
Used in bevy_logic
61KB
1.5K
SLoC
iTriangle
A fast and efficient library for Delaunay triangulation and converting complex polygons into convex shapes, including advanced self-intersection resolution.
Delaunay triangulation
Breaking into convex polygons
Features
- Delaunay Triangulation: Efficient and robust implementation for generating Delaunay triangulations.
- Convex Polygons: Break complex polygons into simpler convex polygons.
- Self-Intersection: Smart intersection resolution with Even-Odd or Non-Zero rules.
Documentation
Getting Started
Add the following to your Cargo.toml:
[dependencies]
i_triangle = "^0.25.0"
After that, represent your polygon as an array of vertices. Here's an example of a cheese polygon:
let shape = [
[ // body
F64Point::new(0.0, 20.0), // 0
F64Point::new(8.0, 10.0), // 1
F64Point::new(7.0, 6.0), // 2
F64Point::new(9.0, 1.0), // 3
F64Point::new(13.0, -1.0), // 4
F64Point::new(17.0, 1.0), // 5
F64Point::new(26.0, -7.0), // 6
F64Point::new(14.0, -15.0), // 7
F64Point::new(0.0, -18.0), // 8
F64Point::new(-14.0, -15.0), // 9
F64Point::new(-25.0, -7.0), // 10
F64Point::new(-18.0, 0.0), // 11
F64Point::new(-16.0, -3.0), // 12
F64Point::new(-13.0, -4.0), // 13
F64Point::new(-8.0, -2.0), // 14
F64Point::new(-6.0, 2.0), // 15
F64Point::new(-7.0, 6.0), // 16
F64Point::new(-10.0, 8.0) // 17
].to_vec(),
[ // hole
F64Point::new(2.0, 0.0), // 18
F64Point::new(-2.0, -2.0), // 19
F64Point::new(-4.0, -5.0), // 20
F64Point::new(-2.0, -9.0), // 21
F64Point::new(2.0, -11.0), // 22
F64Point::new(5.0, -9.0), // 23
F64Point::new(7.0, -5.0), // 24
F64Point::new(5.0, -2.0) // 25
].to_vec()
].to_vec();
let triangulation = shape.to_triangulation(Some(FillRule::NonZero), 0.0);
println!("points: {:?}", triangulation.points);
println!("indices: {:?}", triangulation.indices);
Output Triangulation: triangles indices and vertices, where all triangles oriented in a clockwise direction.
Dependencies
~0.7–1.3MB
~30K SLoC