关于C语言Bresenham直线算法异常问题的技术问询

嘿，我来帮你捋捋这个Bresenham算法的问题！你遇到的情况很典型——当终点y值从40改成20后算法突然失效，核心原因大概率是你的代码没处理斜率绝对值大于1的情况，以及dy为负的符号问题。咱们一步步分析：

为什么(120,40)能正常工作？ #

先看两组参数的差值：

• 第一组：dx=120-10=110，dy=40-150=-110，|dy|=|dx|，斜率绝对值是1，这时候不管算法有没有处理斜率大于1的逻辑，误差项的更新刚好能覆盖每一步的像素，所以能正常绘制。
• 第二组：dx=110，dy=20-150=-130，|dy|=130>110，斜率绝对值≈1.18>1，这时候如果你的代码没做特殊处理，就会出现像素丢失或者绘制错误。

你的代码可能缺失的关键逻辑 #

从你给出的代码片段来看，只定义了dx、dy，但没处理以下两个核心点：

1. 方向符号与绝对值处理 #

Bresenham算法需要先确定x和y的步进方向（是递增还是递减），然后用绝对值计算误差项，否则当dy为负（比如你的第二组参数）时，误差更新逻辑会完全错误。你需要补充：

// 确定x和y的步进方向（1为递增，-1为递减）
int sx = dx > 0 ? 1 : (dx < 0 ? -1 : 0);
int sy = dy > 0 ? 1 : (dy < 0 ? -1 : 0);

// 取dx和dy的绝对值，统一处理误差项
dx = abs(dx);
dy = abs(dy);

2. 斜率绝对值大于1的交换处理 #

当|dy|>|dx|时，算法需要交换x和y的遍历逻辑——因为这时候y方向的步进次数比x多，我们需要以y为主要遍历轴，否则会导致像素绘制不全。你需要添加交换判断：

int swapped = 0;
if (dy > dx) {
    // 交换当前x、y，以及起点终点的x、y，还有dx、dy
    swap(&x, &y);
    swap(&line->start.x, &line->start.y);
    swap(&line->end.x, &line->end.y);
    swap(&dx, &dy);
    swapped = 1;
}

同时在绘制像素时，要根据swapped标记还原正确的坐标：

if (swapped) {
    // 交换后，原y对应现在的x，原x对应现在的y
    drawPixel(monitor, y, x, line->color);
} else {
    drawPixel(monitor, x, y, line->color);
}

3. 误差项的正确更新 #

标准Bresenham的误差项初始化和更新逻辑要配合上面的处理：

int error = 2 * dy - dx;

for (int i = 0; i <= dx; i++) {
    // 绘制像素（上面的判断）
    
    if (error >= 0) {
        y += sy;
        error -= 2 * dx;
    }
    error += 2 * dy;
    x += sx;
}

完整修正后的代码示例 #

这里给你一个能覆盖所有情况的完整函数框架，你可以对比自己的代码补全缺失部分：

// 辅助交换函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void drawaLine(Monitor* monitor, Line* line) {
    int x = line->start.x;
    int y = line->start.y;
    int dx = line->end.x - line->start.x;
    int dy = line->end.y - line->start.y;

    // 处理步进方向
    int sx = dx > 0 ? 1 : (dx < 0 ? -1 : 0);
    int sy = dy > 0 ? 1 : (dy < 0 ? -1 : 0);

    // 取绝对值统一计算
    dx = abs(dx);
    dy = abs(dy);

    int swapped = 0;
    // 处理斜率绝对值大于1的情况
    if (dy > dx) {
        swap(&x, &y);
        swap(&line->start.x, &line->start.y);
        swap(&line->end.x, &line->end.y);
        swap(&dx, &dy);
        swapped = 1;
    }

    int error = 2 * dy - dx;

    for (int i = 0; i <= dx; i++) {
        // 绘制正确的像素坐标
        if (swapped) {
            drawPixel(monitor, y, x, line->color);
        } else {
            drawPixel(monitor, x, y, line->color);
        }

        // 更新误差项和坐标
        if (error >= 0) {
            y += sy;
            error -= 2 * dx;
        }
        error += 2 * dy;
        x += sx;
    }
}

把这些逻辑补到你的代码里，再测试(120,20)的情况，应该就能正常绘制直线了。

内容的提问来源于stack exchange，提问作者Norton