#voronoi #geometry #sweepline

bin+lib boostvoronoi

Boost voronoi ported to 100% rust

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

BSL-1.0 license

415KB
8K SLoC

Crates.io Documentation Workflow Workflow dependency status

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.

Rusty voronoi

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