1 unstable release

0.1.0 Jun 25, 2021

#1967 in Algorithms

Download history 191/week @ 2024-11-15 215/week @ 2024-11-22 120/week @ 2024-11-29 116/week @ 2024-12-06 125/week @ 2024-12-13 45/week @ 2024-12-20 23/week @ 2024-12-27 87/week @ 2025-01-03 87/week @ 2025-01-10 134/week @ 2025-01-17 76/week @ 2025-01-24 183/week @ 2025-01-31 216/week @ 2025-02-07 313/week @ 2025-02-14 303/week @ 2025-02-21 301/week @ 2025-02-28

1,177 downloads per month
Used in 5 crates (2 directly)

MIT/Apache

105KB
1.5K SLoC

cdt

cdt is a library for calculating Delaunay and constrained Delaunay triangulations.

It is optimized for correctness and speed, using exact predicates to perform point-in-circle and orientation tests.


lib.rs:

cdt is a library for calculating Delaunay and constrained Delaunay triangulations.

It is optimized for correctness and speed, using exact predicates to perform point-in-circle and orientation tests.

Examples

Delaunay triangulation

This triangulates a set of four points in a square

let pts = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)];
let triangles = cdt::triangulate_points(&pts).unwrap();
assert!(triangles.len() == 2);
for t in triangles {
println!("{:?} {:?} {:?}", pts[t.0], pts[t.1], pts[t.2])
}

Constrained Delaunay triangulation

This triangulates an inner and outer square

let pts = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0),
(0.2, 0.2), (0.8, 0.2), (0.8, 0.8), (0.2, 0.8)];
let triangles = cdt::triangulate_contours(&pts,
&[vec![0, 1, 2, 3, 0], vec![4, 5, 6, 7, 4]])
.unwrap();
for t in triangles {
println!("{:?} {:?} {:?}", pts[t.0], pts[t.1], pts[t.2])
}

Crate features

By default, the library uses u32 indexes for internal data structures, to improve performance. If you are planning to triangulate more than 500M points in a single pass, you should enable the long-indexes feature.

Dependencies

~1–1.5MB
~35K SLoC