Rust实现Voronoi图生成（从零开始掌握Rust计算几何与Delaunay三角剖分）

Voronoi 图与 Delaunay 三角剖分的关系

Voronoi 图和 Delaunay 三角剖分 是一对“对偶图”（dual graphs）。也就是说，如果你已经构建了点集的 Delaunay 三角剖分，就可以很容易地从中推导出 Voronoi 图。

• Delaunay 三角剖分：将一组点连接成三角形，使得任意三角形的外接圆内不包含其他点。
• Voronoi 图：每个 Voronoi 顶点是 Delaunay 三角形外接圆的圆心；每条 Voronoi 边垂直平分 Delaunay 边。

因此，我们通常先计算 Delaunay 三角剖分，再转换为 Voronoi 图。

在 Rust 中实现 Voronoi 图

虽然从头实现 Delaunay 算法（如 Bowyer-Watson 算法）很有教育意义，但在实际项目中，我们推荐使用成熟的 Rust 库来简化开发。这里我们使用 spade 这个高性能的计算几何库。

第 1 步：创建 Rust 项目

cargo new rust_voronoi_tutorialcd rust_voronoi_tutorial

第 2 步：添加依赖

编辑 Cargo.toml，加入 spade 库：

[dependencies]spade = "1.9"

第 3 步：编写代码生成 Voronoi 图

在 src/main.rs 中写入以下代码：

use spade::rtree::{RTree};use spade::delaunay::{DelaunayTriangulation, TriangulationWalkLocate};use spade::{PointN, Point2};fn main() {    // 定义一组二维种子点    let points: Vec<Point2<f64>> = vec![        Point2::new(1.0, 1.0),        Point2::new(3.0, 2.0),        Point2::new(2.0, 4.0),        Point2::new(5.0, 3.0),        Point2::new(4.0, 1.0),    ];    // 构建 Delaunay 三角剖分    let mut triangulation = DelaunayTriangulation::with_walk_locate();    for point in &points {        triangulation.insert(*point).unwrap();    }    println!("Delaunay 三角形数量: {}", triangulation.num_triangles());    // 遍历所有三角形，获取其外接圆圆心（即 Voronoi 顶点）    for triangle in triangulation.triangles() {        if let Some(circumcenter) = triangulation.circumcenter(triangle) {            println!("Voronoi 顶点: ({:.2}, {:.2})", circumcenter.x(), circumcenter.y());        }    }    // 注意：完整的 Voronoi 图还需要处理无限边（位于凸包上的边）    // spade 提供了 VoronoiDiagram 类型，可直接使用    let voronoi = triangulation.into_voronoi_diagram().unwrap();    println!("\nVoronoi 区域数量: {}", voronoi.regions().len());    for (i, region) in voronoi.regions().iter().enumerate() {        println!("区域 {}: 拥有 {} 条边", i, region.edges().len());    }}

第 4 步：运行程序

cargo run

你将看到输出的 Voronoi 顶点和每个区域的边数。这说明你已成功用 Rust 生成了 Voronoi 图！

为什么选择 Rust 实现计算几何？

Rust 的内存安全、零成本抽象和并发模型使其非常适合高性能计算任务。在处理大规模点集时，Rust计算几何 库（如 spade、nalgebra）能提供接近 C++ 的性能，同时避免空指针、缓冲区溢出等常见错误。

进阶建议

• 尝试可视化 Voronoi 图（可结合 plotters 或导出 SVG）
• 研究如何处理 Voronoi 图的无限边（通常用“虚拟顶点”表示）
• 探索更高维的 Voronoi 图（3D 或 nD）

总结

通过本篇 Rust算法教程，你已经掌握了使用 Rust 生成 Voronoi 图的基本方法。核心在于理解 Voronoi 图与 Delaunay 三角剖分的对偶关系，并借助 spade 这样的高质量库快速实现功能。无论你是做游戏开发、GIS 系统还是科研项目，Rust Voronoi图 都将成为你工具箱中的利器。

现在，动手试试吧！修改种子点，观察 Voronoi 区域的变化，深入理解这一经典计算几何结构。