#delaunay-triangulation #triangulation #mesh #constrained #points #idiomatic #cpp

poly2tri-rs

An idiomatic and fast Constrained Delaunay Triangulation library

3 releases

0.1.2 Mar 20, 2023
0.1.1 Mar 18, 2023
0.1.0 Mar 17, 2023

#160 in Geospatial

MIT/Apache

440KB
3K SLoC

poly2tri-rs

An idiomatic and fast(not just because the language) rust porting for poly2tri cpp project. It calculates CDT (Constrained Delaunay Triangulation) on a polygon.

Install

Add following to cargo.toml

[dependencies]
poly2tri-rs = "0.1"

Or

cargo add poly2tri-rs

Features

  • Multiple hole and steiner points
  • Fast
  • Test coverage, there are both stable and random tests(prop test). Actually discovered and fixed several bugs from cpp lib.

Performance

Introduced a bunch of perf optimizations to meet the cpp version, without breaking the type system.

Timing at the time of writing on my m1 mbp:

example poly2tri-rs poly2tri (cpp) point count
bird 0.08ms 0.17ms 275
debug 0.06ms 0.14ms 200
nazca_heron 0.4ms 0.55ms 1036
nazca_monkey 0.52ms 0.76ms 1204

Limitations

  • Only one polyline supported. For multiple polyline, need to preprocess them.
  • Duplicate point not supported. (yet)

Examples

A square with a hole

Picture

cargo run --example square && open square_with_hole.svg

Sample code

fn example() {
    // randomly generate steinier points (point with no edge)
    let mut points = Vec::<Point>::new();
    for _ in 0..100 {
        let x: f64 = rand::thread_rng().gen_range(0.0..800.);
        let y: f64 = rand::thread_rng().gen_range(0.0..800.);
        points.push(Point::new(x, y));
    }

    // outer square
    let builder = SweeperBuilder::new(vec![
        Point::new(-10., -10.),
        Point::new(810., -10.),
        Point::new(810., 810.),
        Point::new(-10., 810.),
    ])
    .add_steiner_points(points)
    // square hole
    .add_hole(vec![
        Point::new(400., 400.),
        Point::new(600., 400.),
        Point::new(600., 600.),
        Point::new(400., 600.),
    ]);

    // consume builder and grab a sweeper
    let sweeper = builder.build();

    // triangulate with cdt
    let triangles = sweeper.triangulate();

    // draw
    draw(triangles, "square_with_hole.svg".into());
}

Draw test data from poly2tri's testbed

# clone repos
git clone git@github.com:jhasse/poly2tri.git
git clone git@github.com:shuoli84/poly2tri-rs.git

cd poly2tri-rs
cargo run --example draw --release -- --path ../poly2tri/testbed/data/funny.dat --output funny.svg 

# open the svg
open funny.svg

Dependencies

~0.7–1.2MB
~19K SLoC