boostvoronoi 0.12.0

Boost voronoi ported to 100% rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

![Rusty voronoi](img/title.png)

[![crates.io](https://img.shields.io/crates/v/boostvoronoi.svg)](https://crates.io/crates/boostvoronoi)
[![Documentation](https://docs.rs/boostvoronoi/badge.svg)](https://docs.rs/boostvoronoi)
[![status-badge](https://ci.codeberg.org/api/badges/12854/status.svg)](https://ci.codeberg.org/repos/12854)
[![dependency status](https://deps.rs/crate/boostvoronoi/0.12.0/status.svg)](https://deps.rs/crate/boostvoronoi/0.12.0)
![license](https://img.shields.io/crates/l/boostvoronoi)

# Segmented Voronoi for Rust

[Boost 1.76.0 polygon::voronoi](https://www.boost.org/doc/libs/1_76_0/libs/polygon/doc/voronoi_main.htm) ported to 100% rust.
This implementation of [Fortune's algorithm](https://en.wikipedia.org/wiki/Fortune%27s_algorithm) works for line segments as well as points, making it useful for calculating centerlines [(like the title image above)](https://github.com/eadf/toxicblend.rs).

Code still in development, there are still bugs. However, all the remaining bugs I've noticed are also present in C++ boost voronoi.

Gui example:
```sh
cargo run --example fltk_gui
```
* Mouse click to place new points. 
* Press and hold 'L' + mouse click to add a 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::prelude::*;

type I = i32; // this is the integer input type

fn main() -> Result<(), BvError> {
    // Only unique Points will be used. Points should not
    // intersect lines.
    let points: [[I; 2]; 1] = [[9, 10]];
    // Lines may only intersect at the endpoints.
    let segments: [[I; 4]; 1] = [[10, 11, 12, 33]];
    let diagram = Builder::<I>::default()
        // You will have to keep track of the input geometry. it
        // will be referenced as input geometry indices in the
        // output.
        // `with_vertices()` accepts iterators of anything that
        // implements `Into<boostvoronoi::Point>`
        .with_vertices(points.iter())?
        // `with_segments()` accepts iterators of anything that
        //  implements `Into<boostvoronoi::Line>`
        .with_segments(segments.iter())?
        // this will generate the list of cells, edges and circle
        // events (aka vertices)
        .build()?;
    println!(
        "Result: cells:{}, edges:{}, vertices:{}",
        diagram.cells().len(),
        diagram.edges().len(),
        diagram.vertices().len()
    );
    for cell in diagram.cells().iter() {
        println!("Cell : {:?}", cell.id());
        for edge_id in diagram.cell_edge_iterator(cell.id()) {
            let edge = diagram.edge(edge_id)?;
            // The vertices of an edge will have the value `None`
            // if they are infinitely far away.
            println!(
                "  edge: {edge_id:?}, from:{:?} to:{:?}",
                edge.vertex0(),
                diagram.edge_get_vertex1(edge_id)?
            );
        }
    }
    Ok(())
}
```
Edges will become curves when line segments are used as input, see the example code for discretization and interpolation. 

### Minimum Supported Rust Version (MSRV)

The minimum supported version of Rust for `boostvoronoi` is `1.87.0`.


## Todo
- [ ] Try to fix the known problems in C++ Boost voronoi and port over.
- [ ] Add many more test cases for `voronoi_robust_ftp.rs`.
- [ ] Benchmark and optimize.
- [ ] Replace C++ style boolean ordering functors.
- [ ] Replace builtin ulp with some rust crate (approx?).
- [ ] Take care of the `todo:` tags.
- [x] Builder pattern
- [x] Hide implementation details with a workspace (w/o disabling doc-tests)
- [x] Add `serde` to `SyncDiagram` and other diagram types. 
- [x] Specific type conversion tests (`cgmath`,`glam`,`mint` & `geo`)

All credit goes to the original author ([Andrii Sydorchuk](https://github.com/asydorchuk)) and the [boost contributors](https://github.com/boostorg/polygon), except the porting mistakes. They are all mine.