### 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

# 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