Hilbert C语言如何实现？关键步骤是什么？

Hilbert曲线是一种空间填充曲线，由德国数学家大卫·希尔伯特在1891年提出，它最神奇的特点是：一条一维的曲线可以无限地折叠，最终填满整个二维（甚至更高维）的平面，并且曲线上的点是连续的。

在编程领域,用C语言实现Hilbert曲线是一个绝佳的递归算法练习。

什么是Hilbert曲线？

想象一下,一个正方形被分成四个小正方形，Hilbert曲线会以一种特定的“U”形路径遍历这四个小正方形，当每个小正方形被再次细分时，这个“U”形路径会以不同的方向和旋转方式重复。

这个递归的过程可以无限进行下去,生成越来越精细的曲线。

上图展示了从第1阶到第4阶的Hilbert曲线,你可以清晰地看到，每一阶的曲线都是由四个上一阶的曲线以不同方向旋转和连接而成的。

核心思想：递归算法

实现Hilbert曲线的关键在于理解其递归结构,我们可以定义一个函数，它负责在给定的正方形区域内，绘制指定阶数的Hilbert曲线。

这个函数通常需要以下信息：

1. x, y: 当前正方形区域的左上角坐标。
2. size: 当前正方形区域的边长。
3. n: 当前要绘制的Hilbert曲线的阶数。

递归的终止条件：当 n == 0 时，意味着我们到达了最小的单位，只需要在中心点画一个点即可。

递归的步骤：当 n > 0 时，我们将当前的正方形区域分成四个小正方形，并分别调用自身来绘制这四个部分，关键在于，每次调用时，传入的坐标、方向和阶数都不同，以形成最终的“U”形路径。

为了处理不同的旋转方向,我们通常使用一个额外的参数 direction（0=右, 1=上, 2=左, 3=下）来指示当前“U”形开口的方向。

C语言实现代码

下面是一个用C语言实现Hilbert曲线的经典代码示例,这个版本使用 graphics.h 库（在古老的Turbo C或BGI库中）来在图形窗口上绘制曲线，如果你在现代编译器（如GCC）上运行，需要替换为现代的图形库，如 SDL2 或 OpenGL。

使用 graphics.h (经典方式)

#include <graphics.h>
#include <stdio.h>
// 函数声明
void hilbert(int x, int y, int xi, int xj, int yi, int yj, int n);
int main() {
    int gd = DETECT, gm;
    int x = 100, y = 100; // 起始点坐标
    int size = 400;       // 曲线所占区域的边长
    int order = 4;        // Hilbert曲线的阶数
    // 初始化图形模式
    initgraph(&gd, &gm, "");
    // 设置绘图颜色
    setcolor(WHITE);
    // 调用Hilbert曲线函数
    // 参数解释：
    // (x, y): 起始点
    // (xi, xj): x方向的向量，决定了x轴的指向和缩放
    // (yi, yj): y方向的向量，决定了y轴的指向和缩放
    // n: 递归深度（阶数）
    // 初始时，x轴向量为(size, 0)，y轴向量为(0, size)
    hilbert(x, y, size, 0, 0, size, order);
    // 按任意键关闭图形窗口
    getch();
    closegraph();
    return 0;
}
/**
 * @brief 递归绘制Hilbert曲线
 * @param x 当前区域的左上角x坐标
 * @param y 当前区域的左上角y坐标
 * @param xi x方向向量的x分量
 * @param xj x方向向量的y分量
 * @param yi y方向向量的x分量
 * @param yj y方向向量的y分量
 * @param n 递归深度
 */
void hilbert(int x, int y, int xi, int xj, int yi, int yj, int n) {
    if (n <= 0) {
        // 递归终止：在当前点画一个点
        // 实际坐标是 (x + xi/2, y + yj/2)
        putpixel(x + (xi / 2), y + (yj / 2), WHITE);
    } else {
        // 递归绘制四个部分，形成“U”形
        // A部分：向左旋转，递归深度减1
        hilbert(x, y, yi / 2, yj / 2, xi / 2, xj / 2, n - 1);
        // B部分：向上移动，递归深度减1
        hilbert(x + xi / 2, y + xj / 2, xi / 2, xj / 2, yi / 2, yj / 2, n - 1);
        // C部分：向右移动，递归深度减1
        hilbert(x + xi / 2 + yi / 2, y + xj / 2 + yj / 2, xi / 2, xj / 2, yi / 2, yj / 2, n - 1);
        // D部分：向右旋转，递归深度减1
        hilbert(x + xi / 2 + yi, y + xj / 2 + yj, -yi / 2, -yj / 2, -xi / 2, -xj / 2, n - 1);
    }
}

代码解释：

• main() 函数负责初始化图形窗口，设置参数，并启动递归过程。
• hilbert() 是核心函数，它通过坐标和向量来定义当前的正方形区域和方向。
  • 向量 (xi, xj) 和 (yi, yj) 描述了如何从当前点 (x, y) 到达正方形的四个角，这是一种非常优雅的参数化表示方法。
  • 当 n 减少到0时，我们在当前区域的中心画一个点。
  • 否则,我们按照A-D的顺序调用四次自身，每次调用都调整了坐标和向量，从而实现了不同方向的旋转和移动，最终拼接成一个大的“U”形。

现代实现：使用 SDL2 库

graphics.h 已经过时，在现代C/C++开发中，我们使用更强大的库如 SDL2，下面是一个使用SDL2的示例，它可以在Windows, Linux, macOS上运行。

准备工作：你需要安装SDL2开发库，在Linux上（如Ubuntu），可以使用 sudo apt-get install libsdl2-dev。

#include <stdio.h>
#include <SDL2/SDL.h>
// 窗口设置
const int WINDOW_WIDTH = 800;
const int WINDOW_HEIGHT = 800;
const int MAX_ORDER = 7; // 最大阶数，防止栈溢出和绘制时间过长
// SDL全局变量
SDL_Window* gWindow = NULL;
SDL_Renderer* gRenderer = NULL;
/**
 * @brief 使用SDL绘制Hilbert曲线
 * @param x 当前区域的左上角x坐标
 * @param y 当前区域的左上角y坐标
 * @param size 当前区域的边长
 * @param n 递归深度（阶数）
 */
void drawHilbert(int x, int y, int size, int n) {
    if (n <= 0) {
        // 递归终止：画一个点
        SDL_RenderDrawPoint(gRenderer, x + size / 2, y + size / 2);
        return;
    }
    int newSize = size / 2;
    // A部分：左下角，逆时针旋转
    drawHilbert(x, y + newSize, newSize, n - 1);
    // B部分：左上角
    drawHilbert(x, y, newSize, n - 1);
    // C部分：右上角
    drawHilbert(x + newSize, y, newSize, n - 1);
    // D部分：右下角，顺时针旋转
    drawHilbert(x + newSize, y + newSize, newSize, n - 1);
}
int main(int argc, char* argv[]) {
    // 1. 初始化SDL
    if (SDL_Init(SDL_INIT_VIDEO) < 0) {
        printf("SDL could not initialize! SDL_Error: %s\n", SDL_GetError());
        return 1;
    }
    // 2. 创建窗口
    gWindow = SDL_CreateWindow("Hilbert Curve - C Language",
                               SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED,
                               WINDOW_WIDTH, WINDOW_HEIGHT,
                               SDL_WINDOW_SHOWN);
    if (gWindow == NULL) {
        printf("Window could not be created! SDL_Error: %s\n", SDL_GetError());
        return 1;
    }
    // 3. 创建渲染器
    gRenderer = SDL_CreateRenderer(gWindow, -1, SDL_RENDERER_ACCELERATED);
    if (gRenderer == NULL) {
        printf("Renderer could not be created! SDL_Error: %s\n", SDL_GetError());
        return 1;
    }
    // 设置绘制颜色为白色
    SDL_SetRenderDrawColor(gRenderer, 255, 255, 255, 255);
    // 4. 主循环
    bool quit = false;
    SDL_Event e;
    int order = 1; // 初始阶数
    while (!quit) {
        // 处理事件
        while (SDL_PollEvent(&e) != 0) {
            if (e.type == SDL_QUIT) {
                quit = true;
            } else if (e.type == SDL_KEYDOWN) {
                if (e.key.keysym.sym == SDLK_UP && order < MAX_ORDER) {
                    order++;
                } else if (e.key.keysym.sym == SDLK_DOWN && order > 1) {
                    order--;
                }
            }
        }
        // 清空渲染器（用黑色填充）
        SDL_SetRenderDrawColor(gRenderer, 0, 0, 0, 255);
        SDL_RenderClear(gRenderer);
        // 重新设置绘制颜色为白色
        SDL_SetRenderDrawColor(gRenderer, 255, 255, 255, 255);
        // 绘制Hilbert曲线
        drawHilbert(50, 50, WINDOW_WIDTH - 100, order);
        // 更新屏幕
        SDL_RenderPresent(gRenderer);
        // 简单的延迟，避免CPU占用过高
        SDL_Delay(16); // ~60 FPS
    }
    // 5. 清理资源
    SDL_DestroyRenderer(gRenderer);
    SDL_DestroyWindow(gWindow);
    SDL_Quit();
    return 0;
}

SDL2版本特点：

• 更现代：跨平台，性能更好，是游戏和图形应用开发的标准之一。
• 交互性：增加了键盘事件（上下箭头键）来动态改变曲线的阶数，让你能直观地看到曲线是如何变化的。
• 更清晰：递归逻辑简化了，直接使用 x, y, size 来定义区域，更易于理解。

Hilbert曲线的应用

虽然它看起来像一个数学玩具,但Hilbert曲线在计算机科学和工程中有许多实际应用：

1. 图像处理：将二维像素映射到一维数组，保持空间局部性，这意味着相邻的像素在数组中也是相邻的（或接近的），这对于图像压缩和缓存优化非常有用。
2. 数据库索引：在多维数据库（如地理信息系统GIS）中，使用Hilbert曲线对多维数据进行排序，可以使得在空间上接近的数据在索引中也接近，从而提高范围查询的效率。
3. 路由问题：在需要遍历网格状结构（如芯片布线、机器人路径规划）时，Hilbert曲线提供了一种高效且无交叉的遍历路径。
4. 分形艺术：其自相似性使其成为生成美丽分形图案的基础。

在C语言中,“Hilbert”通常指用递归算法绘制Hilbert曲线，这个问题完美地展示了递归思想的强大和优雅，从经典的 graphics.h 到现代的 SDL2，实现方式在变，但其核心的递归逻辑不变，掌握它不仅能提升你的C语言编程能力，也能让你对递归和分形几何有更深的理解。