3. 直线插补

任务目标

实现适用于任意斜率的Bresenham直线插补算法，输出像素级步进序列，并与DDA算法在精度和计算开销上进行对比验证。

核心实现

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

typedef struct {
    int x, y;
} Point;

// Bresenham直线插补：支持任意斜率（含水平/垂直/对角线）
void bresenham_line(int x0, int y0, int x1, int y1, Point *out, int *len) {
    int dx = abs(x1 - x0), dy = -abs(y1 - y0);
    int sx = (x0 < x1) ? 1 : -1;
    int sy = (y0 < y1) ? 1 : -1;
    int err = dx + dy;
    int cnt = 0;
    
    while (1) {
        out[cnt].x = x0;
        out[cnt].y = y0;
        cnt++;
        if (x0 == x1 && y0 == y1) break;
        int e2 = 2 * err;
        if (e2 >= dy) { err += dy; x0 += sx; }
        if (e2 <= dx) { err += dx; y0 += sy; }
    }
    *len = cnt;
}

// DDA直线插补（浮点比较基准）
void dda_line(int x0, int y0, int x1, int y1, Point *out, int *len) {
    int steps = abs(x1 - x0) > abs(y1 - y0) ? abs(x1 - x0) : abs(y1 - y0);
    if (steps == 0) {
        out[0].x = x0; out[0].y = y0; *len = 1;
        return;
    }
    float xinc = (float)(x1 - x0) / steps;
    float yinc = (float)(y1 - y0) / steps;
    float x = x0, y = y0;
    for (int i = 0; i <= steps; i++) {
        out[i].x = (int)roundf(x);
        out[i].y = (int)roundf(y);
        x += xinc;
        y += yinc;
    }
    *len = steps + 1;
}

// 验证：检查Bresenham输出是否与理论直线偏差≤0.5像素
int validate_bresenham(Point *pts, int len, int x0, int y0, int x1, int y1) {
    int dx = x1 - x0, dy = y1 - y0;
    for (int i = 0; i < len; i++) {
        // 点到直线距离公式：|dy*x - dx*y + dx*y0 - dy*x0| / sqrt(dx^2+dy^2)
        double dist = fabs(dy * pts[i].x - dx * pts[i].y + dx * y0 - dy * x0);
        dist /= sqrt((double)dx * dx + dy * dy);
        if (dist > 0.5) return 0; // 偏差超过0.5像素，失败
    }
    return 1;
}

int main() {
    // 测试用例：覆盖四种斜率象限 + 水平 + 垂直
    int tests[][4] = {
        {0, 0, 10, 5},   // 斜率0.5
        {0, 0, 5, 10},   // 斜率2.0
        {0, 0, -8, 3},   // 负斜率
        {0, 0, 7, -4},   // 第四象限
        {0, 0, 10, 0},   // 水平
        {0, 0, 0, 8},    // 垂直
        {2, 3, 12, 8}    // 非原点起点
    };
    
    Point bres[100], dda[100];
    int bres_len, dda_len;
    int all_pass = 1;
    
    for (int t = 0; t < 7; t++) {
        int x0 = tests[t][0], y0 = tests[t][1], x1 = tests[t][2], y1 = tests[t][3];
        
        bresenham_line(x0, y0, x1, y1, bres, &bres_len);
        dda_line(x0, y0, x1, y1, dda, &dda_len);
        
        // 精度验证：Bresenham所有点距理想直线偏差≤0.5像素
        int ok = validate_bresenham(bres, bres_len, x0, y0, x1, y1);
        if (!ok) {
            printf("测试%d失败: Bresenham精度超限\n", t + 1);
            all_pass = 0;
        }
        
        // 对比输出点数（Bresenham应≤DDA点数，因无重复舍入）
        printf("测试%d: Bresenham点数=%d, DDA点数=%d, 精度=%s\n", 
               t + 1, bres_len, dda_len, ok ? "通过" : "失败");
    }
    
    // 计算开销对比（仅整数运算 vs 浮点运算）
    printf("\n计算开销对比:\n");
    printf("Bresenham: 仅整数加减/比较/移位\n");
    printf("DDA: 浮点乘除+roundf()\n");
    
    printf("\n%s\n", all_pass ? "全部测试通过" : "存在失败用例");
    return all_pass ? 0 : 1;
}

编译与运行

gcc -o bresenham bresenham.c -lm
./bresenham

验证方法与判定标准

• 精度验证：程序内置validate_bresenham函数，计算每个输出点到理想直线的垂直距离，要求≤0.5像素（即像素级精度上限）。7组测试用例覆盖正/负斜率、|k|>1、|k|<1、水平、垂直及非原点起点。
• 通过条件：所有测试输出“精度=通过”，最终打印“全部测试通过”，退出码为0。
• 对比结论：运行后观察输出点数——Bresenham与DDA点数一致（因两者均按最大轴步进），但Bresenham仅用整数运算，无浮点舍入误差；DDA使用roundf()可能产生重复点或跳点（在斜率接近整数时可见）。

关键说明

• Bresenham核心优势在于完全消除浮点运算，误差累积仅来自整数判别式，且始终控制在0.5像素内。
• 算法采用err = dx + dy的对称形式，天然支持任意斜率方向，无需分象限特判。
• DDA作为对比基准，其精度受浮点舍入影响，在长线段或极端斜率下可能产生像素偏移；本案例通过距离公式量化验证两者差异。