Voronoi图算法详解（C语言从零实现Voronoi图：小白也能掌握的计算几何入门教程）

为什么学习Voronoi图？

Voronoi图是计算几何算法中的经典问题，掌握它不仅能提升你的算法思维，还能为后续学习Delaunay三角剖分、空间分析等打下基础。对于初学者来说，这也是理解“分治”和“距离比较”思想的好例子。

C语言实现思路

由于完整的Voronoi图构建（如Fortune算法）较为复杂，本文采用一种适合初学者Voronoi教程的暴力方法：遍历图像中的每个像素，计算它到所有种子点的距离，归属最近的种子点。

这种方法虽然效率不高，但逻辑清晰，非常适合教学目的。

完整C语言代码示例

下面是一个使用控制台输出简易Voronoi图的C程序：

#include <stdio.h>#include <math.h>#define WIDTH  80#define HEIGHT 25#define NUM_POINTS 5// 种子点结构typedef struct {    int x, y;} Point;// 计算两点间欧氏距离的平方（避免开方提高效率）double dist_sq(int x1, int y1, int x2, int y2) {    int dx = x1 - x2;    int dy = y1 - y2;    return dx * dx + dy * dy;}int main() {    // 定义5个种子点（你可以修改这些坐标）    Point seeds[NUM_POINTS] = {        {10, 5},        {70, 8},        {40, 15},        {20, 20},        {60, 22}    };    // 遍历屏幕上的每个“像素”    for (int y = 0; y < HEIGHT; y++) {        for (int x = 0; x < WIDTH; x++) {            int closest = 0;            double min_dist = dist_sq(x, y, seeds[0].x, seeds[0].y);            // 找到最近的种子点            for (int i = 1; i < NUM_POINTS; i++) {                double d = dist_sq(x, y, seeds[i].x, seeds[i].y);                if (d < min_dist) {                    min_dist = d;                    closest = i;                }            }            // 用不同字符表示不同区域            char symbols[] = {'*', '#', '@', '%', '&'};            putchar(symbols[closest]);        }        putchar('\n');    }    return 0;}

代码说明

• 种子点定义：我们用结构体 Point 存储每个种子点的坐标。
• 距离计算：使用距离的平方（dist_sq）避免浮点运算，提高效率。
• 暴力匹配：对每个像素点，遍历所有种子点，找到最近的一个。
• 可视化：用不同字符（*, # 等）代表不同Voronoi区域。

运行效果与优化建议

编译并运行上述代码，你将在终端看到一个由不同符号组成的Voronoi图。虽然粗糙，但它清晰展示了区域划分的概念。

如果你想进一步提升，可以：

• 将输出保存为PPM图像格式，用图片查看器打开；
• 改用更高效的算法（如Fortune's algorithm）处理大量点；
• 添加颜色支持（需结合图形库如SDL或OpenGL）。

总结

通过这个简单的C语言程序，你已经掌握了Voronoi图算法的基本原理和实现方式。虽然这只是入门级实现，但它为你打开了计算几何算法的大门。坚持练习，你很快就能挑战更复杂的图形算法！

记住：每一个复杂的图形，都始于一个简单的点。