Rust的分割Voronoi

Boost 1.76.0 polygon::voronoi 完全移植到100% rust。此实现使用 Fortune算法，适用于线段以及点，可用于计算中心线 (如上图标题所示)。

代码仍在开发中，仍然存在错误。然而，我注意到的所有剩余错误也存在于C++ boost voronoi中。

Gui示例

cargo run --example fltk_gui

• 鼠标点击放置新点。
• 按住 'L' + 鼠标点击以添加单条线。
• 按住 'S' + 鼠标点击以添加线串。
• 使用鼠标滚轮缩放。
• 鼠标点击并拖动以平移。

API示例

use boostvoronoi::prelude::*;

type I = i32; // this is the integer input type
type F = f64; // this is the float output type

fn main() -> Result<(), BvError> {
    // Only unique Points will be used. Points should not
    // intersect lines.
    let p = vec!([9_i32, 10]);
    // Lines may only intersect at the endpoints.
    let s = vec!([10_i32, 11, 12, 33]);
    let diagram = Builder::<I, F>::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(p.iter())?
        // `with_segments()` accepts iterators of anything that
        //  implements `Into<boostvoronoi::Line>`
        .with_segments(s.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()
    );
    // The values inside the diagram are wrapped in `Rc<Cell<T>>`
    for cell in diagram.cells().iter().map(|c| c.get()) {
        println!("Cell : {}", cell.id().0);
        for edge_id in diagram.cell_edge_iterator(cell.id()) {
            let edge = diagram.get_edge(edge_id)?.get();
            // The vertices of an edge will have the value `None`
            // if they are infinitely far away.
            println!(
                "  edge: {}, from:{:?} to:{:?}",
                edge_id.0,
                edge.vertex0(),
                diagram.edge_get_vertex1(edge_id)?
            );
        }
    }
    Ok(())
}

当使用线段作为输入时，边缘将变为曲线，请参阅示例代码以了解离散化和插值。

最低支持的Rust版本 (MSRV)

boostvoronoi 最低支持的Rust版本是 1.66。

待办事项

• 尝试修复C++ Boost voronoi中的已知问题并移植。
• 为 voronoi_robust_ftp.rs 添加更多测试用例。
• 基准测试和优化。
• 替换C++风格布尔排序函数。
• 替换内置ulp为某些rust crate（approx?）。
• 注意 todo: 标签。
• 构建器模式
• 使用工作空间（不禁用doc-tests）隐藏实现细节
• 将 serde 添加到 SyncDiagram 和其他图表类型。
• 特定类型转换测试 (cgmath,glam,mint & geo）

所有功劳都属于原始作者 (Andrii Sydorchuk) 和 boost贡献者，除了移植错误。它们都是我的。