089. 编写代码实现简单的图形处理算法

在C语言中实现简单的图形处理算法，可以通过一些基本的图形绘制操作来完成。这里以一个简单的图形绘制程序为例，展示如何使用C语言绘制基本的图形，如直线、矩形和圆形。我们将使用一个简单的字符图形界面来实现这些功能。

示例代码：简单的图形处理程序

#include <stdio.h>
#include <math.h>

#define WIDTH 50
#define HEIGHT 20

char screen[HEIGHT][WIDTH]; // 定义屏幕数组

// 初始化屏幕
void initScreen() {
    for (int i = 0; i < HEIGHT; i++) {
        for (int j = 0; j < WIDTH; j++) {
            screen[i][j] = ' '; // 用空格初始化屏幕
        }
    }
}

// 绘制点
void drawPoint(int x, int y, char c) {
    if (x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT) {
        screen[y][x] = c;
    }
}

// 绘制直线（使用Bresenham算法）
void drawLine(int x0, int y0, int x1, int y1, char c) {
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int sx = (x0 < x1) ? 1 : -1;
    int sy = (y0 < y1) ? 1 : -1;
    int err = (dx > dy) ? dx : -dy;
    int e2;

    while (1) {
        drawPoint(x0, y0, c);
        if (x0 == x1 && y0 == y1) break;
        e2 = err;
        if (e2 > -dx) {
            err -= dy;
            x0 += sx;
        }
        if (e2 < dy) {
            err += dx;
            y0 += sy;
        }
    }
}

// 绘制矩形
void drawRectangle(int x, int y, int width, int height, char c) {
    for (int i = y; i < y + height; i++) {
        for (int j = x; j < x + width; j++) {
            drawPoint(j, i, c);
        }
    }
}

// 绘制圆形（使用中点圆算法）
void drawCircle(int x0, int y0, int radius, char c) {
    int x = radius;
    int y = 0;
    int radiusError = 1 - x;

    while (x >= y) {
        drawPoint(x0 + x, y0 + y, c);
        drawPoint(x0 + y, y0 + x, c);
        drawPoint(x0 - y, y0 + x, c);
        drawPoint(x0 - x, y0 + y, c);
        drawPoint(x0 - x, y0 - y, c);
        drawPoint(x0 - y, y0 - x, c);
        drawPoint(x0 + y, y0 - x, c);
        drawPoint(x0 + x, y0 - y, c);

        y++;
        if (radiusError < 0) {
            radiusError += 2 * y + 3;
        } else {
            x--;
            radiusError += 2 * (y - x) + 5;
        }
    }
}

// 显示屏幕
void displayScreen() {
    for (int i = 0; i < HEIGHT; i++) {
        for (int j = 0; j < WIDTH; j++) {
            putchar(screen[i][j]);
        }
        putchar('\n');
    }
}

int main() {
    initScreen();

    // 绘制直线
    drawLine(5, 5, 20, 15, '*');

    // 绘制矩形
    drawRectangle(25, 5, 10, 5, '#');

    // 绘制圆形
    drawCircle(40, 10, 5, '@');

    displayScreen();

    return 0;
}

代码说明

屏幕初始化：使用一个二维字符数组 screen 来表示屏幕，初始化为空格。
绘制点：在指定位置 (x, y) 绘制字符 c。
绘制直线：使用Bresenham算法绘制直线，适用于整数坐标点。
绘制矩形：在指定位置 (x, y) 绘制一个宽度为 width、高度为 height 的矩形。
绘制圆形：使用中点圆算法绘制圆形，适用于整数坐标点。
显示屏幕：遍历屏幕数组，逐行输出字符。

在计算机图形学中，直线和圆形的绘制是基本的图形处理任务。以下是两种经典的绘制算法：Bresenham直线算法和中点圆算法（也称为Bresenham圆算法）。这些算法都是基于离散点的绘制方法，特别适合在像素化的屏幕上绘制图形。

1. Bresenham直线算法

Bresenham直线算法是一种高效的直线绘制算法，它通过逐像素地计算直线路径上的点，避免了浮点运算，从而提高了绘制速度。

算法原理

假设要绘制一条从点 (x0,y0) 到点 (x1,y1) 的直线。Bresenham算法的核心思想是通过决策变量 d 来判断下一个像素点的位置。

决策变量 d：用于决定下一个像素点是向右移动（水平方向）还是向右上方移动（对角方向）。
斜率 m：直线的斜率，用于判断直线的方向。

根据斜率的不同，可以分为以下几种情况：

斜率 ∣m∣<1：主要沿水平方向绘制。
斜率 ∣m∣>1：主要沿垂直方向绘制。
斜率 ∣m∣=1：沿对角方向绘制。

算法步骤

初始化：

计算水平和垂直方向的步长：dx=∣x1−x0∣,dy=∣y1−y0∣
初始化当前点 (x,y)=(x0,y0)。
初始化决策变量 d：d=2⋅dy−dx(对于斜率小于1的情况)或d=2⋅dx−dy(对于斜率大于1的情况)

绘制点：在当前点 (x,y) 处绘制像素。

更新决策变量：

如果 d<0，下一个点沿水平方向移动：x=x+1,d=d+2⋅dy
如果 d≥0，下一个点沿对角方向移动：x=x+1,y=y+1,d=d+2⋅dy−2⋅dx

重复：重复上述步骤，直到达到终点 (x1,y1)。

代码实现

以下是Bresenham直线算法的C语言实现：

void drawLine(int x0, int y0, int x1, int y1, char c) {
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int sx = (x0 < x1) ? 1 : -1;
    int sy = (y0 < y1) ? 1 : -1;
    int err = (dx > dy) ? dx : -dy;
    int e2;

    while (1) {
        drawPoint(x0, y0, c); // 绘制当前点
        if (x0 == x1 && y0 == y1) break;
        e2 = err;
        if (e2 > -dx) {
            err -= dy;
            x0 += sx;
        }
        if (e2 < dy) {
            err += dx;
            y0 += sy;
        }
    }
}

2. 中点圆算法（Bresenham圆算法）

中点圆算法是一种高效的圆绘制算法，它利用圆的八分对称性，通过逐点计算圆上的像素位置。

算法原理

假设要绘制一个以 (x0,y0) 为中心、半径为 r 的圆。中点圆算法的核心思想是通过决策变量 d 来判断下一个像素点的位置。

决策变量 d：用于决定下一个像素点是沿水平方向移动还是沿对角方向移动。
八分对称性：圆的八分之一部分可以通过对称性扩展到整个圆。

算法步骤

初始化：

初始化当前点 (x,y)=(0,r)。
初始化决策变量 d：d=3−2r

绘制点：

利用八分对称性绘制当前点：

drawPoint(x0+x,y0+y,c)drawPoint(x0+y,y0+x,c)drawPoint(x0−y,y0+x,c)drawPoint(x0−x,y0+y,c)drawPoint(x0−x,y0−y,c)drawPoint(x0−y,y0−x,c)drawPoint(x0+y,y0−x,c)drawPoint(x0+x,y0−y,c)

更新决策变量：

如果 d>0，下一个点沿对角方向移动：x=x+1,y=y−1,d=d+4⋅(x−y)+10
如果 d≤0，下一个点沿水平方向移动：x=x+1,d=d+4⋅x+6

重复：

重复上述步骤，直到 x≥y。

代码实现

void drawCircle(int x0, int y0, int radius, char c) {
    int x = 0;
    int y = radius;
    int d = 3 - 2 * radius;

    while (x <= y) {
        drawPoint(x0 + x, y0 + y, c);
        drawPoint(x0 + y, y0 + x, c);
        drawPoint(x0 - y, y0 + x, c);
        drawPoint(x0 - x, y0 + y, c);
        drawPoint(x0 - x, y0 - y, c);
        drawPoint(x0 - y, y0 - x, c);
        drawPoint(x0 + y, y0 - x, c);
        drawPoint(x0 + x, y0 - y, c);

        if (d > 0) {
            y--;
            d += 4 * (x - y) + 10;
        } else {
            d += 4 * x + 6;
        }
        x++;
    }
}

总结

Bresenham直线算法：适用于绘制直线，通过决策变量避免浮点运算，提高效率。
中点圆算法：适用于绘制圆，利用八分对称性减少计算量，通过决策变量决定像素点的位置。

这两种算法都是计算机图形学中的经典算法，广泛应用于图形绘制和游戏开发中。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)