Voronoi图算法详解（C++实现Voronoi图：从零开始掌握计算几何核心）

为什么学习Voronoi图？

• 用于最近邻搜索（如地图上找最近的加油站）
• 在游戏开发中用于AI寻路或区域控制
• 在无线传感器网络中优化覆盖范围
• 是许多高级几何算法（如Delaunay三角剖分）的基础

Voronoi图的C++实现思路

严格来说，高效生成Voronoi图需要使用Fortune算法（时间复杂度 O(n log n)），但对初学者而言，我们可以采用一种更直观的“暴力法”来理解其原理——即遍历图像中的每个像素，计算它到所有种子点的距离，然后分配给最近的种子点。

虽然这种方法效率较低（O(n × m)，其中 n 是种子点数量，m 是像素数量），但它逻辑清晰，非常适合学习和可视化。

完整C++代码示例

下面是一个使用标准C++（不依赖外部图形库）生成Voronoi图文本表示的简化版本。你可以将其扩展为使用OpenCV或SFML进行图形渲染。

#include <iostream>#include <vector>#include <cmath>#include <limits>struct Point {    double x, y;    Point(double x = 0, double y = 0) : x(x), y(y) {}};double distance(const Point& a, const Point& b) {    return std::sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}// 简化的Voronoi图生成（输出每个像素所属的站点索引）void generateVoronoi(const std::vector<Point>& sites,                     int width, int height) {    for (int y = 0; y < height; ++y) {        for (int x = 0; x < width; ++x) {            int closestSite = 0;            double minDist = std::numeric_limits<double>::max();            for (size_t i = 0; i < sites.size(); ++i) {                double d = distance(Point(x, y), sites[i]);                if (d < minDist) {                    minDist = d;                    closestSite = static_cast<int>(i);                }            }            // 这里可以将 closestSite 映射为颜色并绘图            // 为简化，我们只输出站点编号（模10）            std::cout << (closestSite % 10);        }        std::cout << "\n";    }}int main() {    std::vector<Point> seeds = {        Point(10, 10),        Point(50, 20),        Point(30, 40),        Point(60, 60)    };    int width = 80;    int height = 40;    std::cout << "生成Voronoi图（文本表示）:\n";    generateVoronoi(seeds, width, height);    return 0;}

如何提升性能？

上述暴力法适合教学，但在实际项目中，建议使用成熟的库：

• Boost.Polygon：提供高效的Voronoi图实现
• CGAL（计算几何算法库）：工业级精度与性能
• Qhull：支持高维Voronoi图

总结

通过本教程，你已经掌握了Voronoi图算法的基本概念，并用C++实现了其简化版本。虽然我们使用的是暴力方法，但它帮助你理解了Voronoi图的核心思想：**“就近归属”**。

下一步，你可以尝试：

• 将文本输出改为图形界面（如用OpenCV绘制彩色区域）
• 研究Fortune算法以实现 O(n log n) 的高效生成
• 探索Voronoi图与Delaunay三角剖分的对偶关系

无论你是学习计算几何，还是想在项目中应用Voronoi图生成技术，希望这篇教程为你打下了坚实的基础！