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.

Note

The code uses #![feature(map_first_last)] i.e. rust nightly.

Gui example: fish cargo run --example fltk_gui * Mouse click to place new points. * Press and hold 'L' + mouse click to add single line. * Press and hold 'S' + mouse click to add strings of lines. * Use mouse wheel to zoom. * Mouse click and drag to pan.

API example: ```rust use boostvoronoi::{Point,Line}; use boostvoronoi::builder::{Builder}; type I1 = i32; // this is the integer input type type F1 = f64; // this is the float output type (circle event coordinates)

// Only unique Points will be used. Points should not intersect lines let p = vec![Point{x:9i32, y:10}]; // Lines may only intersect at the endpoints. let s = vec![Line::new(Point{x:10i32, y:11}, Point{x:12, y:13})]; let mut vb = Builder::::new();

// you will have to keep track of the input geometry. it will be referenced as // input geometry indices in the output. vb.withvertices(p.iter()).unwrap(); vb.withsegments(s.iter()).unwrap();

// this will generate the list of cells, edges and circle events (aka vertices) let result = vb.construct().unwrap(); ``` Edges may become curves when line segments are used as input, see the example code for discretization and interpolation.

Todo

• [x] Fix the degenerate vertex key problem
• [ ] Fix the beach-line key problem
• [ ] Error handling
• [X] Evaluate the generic API. Is really needed?
• [ ] ~Replace~ Verify the builtin ulp implementation
• [x] Replace num::BigInt with something lighter
• [ ] Add many more test cases for voronoirobustftp.rs, specially for ulp
• [x] Remove use of vec_map::VecMap where not absolutely needed.
• [ ] Benchmark and optimize
• [x] Example GUI with more features. fltk?
• [x] Fix the beach-line bug found with main.rs example

All credit goes to the original author (Andrii Sydorchuk) and the boost contributors, except the porting mistakes. They are all mine.