6 releases (3 breaking)
new 0.4.1 | Mar 1, 2021 |
---|---|
0.4.0 | Feb 22, 2021 |
0.3.1 | Feb 7, 2021 |
0.3.0 | Jan 28, 2021 |
0.1.0 | Jan 22, 2021 |
#63 in Math
40 downloads per month
Used in centerline
415KB
8K
SLoC
Segmented Voronoi for Rust
Boost 1.75.0 polygon::voronoi ported to 100% rust. This implementation of Fortune's algorithm works on line segments as well as points, making it useful for calculating centerlines.
Code still in development, not ready for any purpose.
Quick example:
set -x LIBRARY_PATH /opt/local/lib/ #or wherever you store your SDL
cargo run --example piston_gui
API example:
type I1 = i32; // this is the integer input type
type F1 = f64; // this is the float output type (circle event coordinates)
type I2 = i64; // All integer calculations are made in this type (or num::BigInt when needed)
type F2 = f64; // All float calculations are made in this type
// it is ok to set I1=I2=i64 and F1=F2=f64
// Points should be unique,
let p = vec![Point{x:9, y:10}];
// Lines should never intersect with other lines.
// The only points that can intersect are the endpoints.
let s = vec![Line::new(Point{x:10, y:11}, Point{x:12, y:13})];
let mut vb = Builder::<I1, F1, I2, F2>::new();
// you will have to keep track of the input geometry. it will be referenced as
// input geometry indices in the output.
vb.with_vertices(p.iter())?;
vb.with_segments(s.iter())?;
// this will generate a the list of cells, edges and circle events (aka vertices)
let result = vb.construct()?;
Edges may become curves when line segments are used as input, see the example code for discretization and interpolation.
Todo
- Error handling
- Evaluate the generic API. Is <I1, F1, I2, F2> really needed?
- Replace the builtin ulp implementation
- Replace num::BigInt with something lighter
- Add many more test cases for voronoi_robust_ftp.rs, specially for ulp
- Remove use of vec_map::VecMap where not absolutely needed.
- Benchmark and optimize
- Example GUI with more features. fltk?
- Fix the beachline bug found with main.rs example
All credit goes to the original author (Andrii Sydorchuk), except the porting mistakes. They are all mine.
Dependencies
~1.2–1.7MB
~40K SLoC