如何修复Python中Kandinsky模块Bresenham算法的非-1负斜率问题？

问题描述 #

基于Python 3.12编写的Bresenham画线程序，使用Numworks计算器内置Kandinsky模块：

• 模块Y轴向下递增，视觉负斜率对应实际正斜率，反之亦然
• 正斜率、±1、0及无穷大斜率的线条均可正常绘制
• 除斜率为-1的负斜率线条外，其他负斜率线条无法正常绘制，表现为仅在x1坐标处保持水平

原代码 #

from kandinsky import *
def draw_line(x1, y1, x2, y2, color):
    if x2 - x1 != 0:
        m = (y2 - y1) / (x2 - x1)
    elif y2 - y1 > 0:
        m = 500
    elif y2 - y1 < 0:
        m = -500
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
    if abs(m) < 1:
        A = 2 * (y2 - y1)
        B = A - 2 * (x2 - x1)
        P = A - (x2 - x1)
        set_pixel(x1, y1, color)
        for i in range(x1 + 1, x2 + 1):
            if P < 0:
                P += A
            else:
                P += B
                if m < 0:
                    y1 -= 1
                else:
                    y1 += 1
            set_pixel(i, y1, color)
    elif abs(m) > 1:
        A = 2 * (x2 - x1)
        B = A - 2 * (y2 - y1)
        P = A - (y2 - y1)
        set_pixel(x1, y1, color)
        for i in range(y1 + 1, y2 + 1):
            if P < 0:
                P += A
            else:
                P += B
                if m < 0:
                    x1 -= 1
                else:
                    x1 += 1
            set_pixel(x1, i, color)
    elif abs(m) == 1:
        for i in range(x1, x2 + 1):
            set_pixel(x1, y1, color)
            x1 += 1
            if m == 1:
                y1 += 1
            else:
                y1 -= 1

问题原因 #

在abs(m) > 1的分支中：

1. 仅统一了x轴的递增方向（x1 < x2），但未处理y轴的方向
2. 当负斜率且|m|>1时，交换x坐标后y2 < y1，导致range(y1 + 1, y2 + 1)为空，循环完全不执行，仅绘制了起始点，看起来是水平线条

修复后的代码 #

from kandinsky import *
def draw_line(x1, y1, x2, y2, color):
    # 计算斜率（用整数判断避免浮点精度问题）
    dx = x2 - x1
    dy = y2 - y1
    if dx != 0:
        m = dy / dx
    elif dy > 0:
        m = 500
    elif dy < 0:
        m = -500
    
    # 统一x轴递增方向
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        dx = -dx
        dy = -dy
    
    if abs(m) < 1:
        A = 2 * dy
        B = A - 2 * dx
        P = A - dx
        set_pixel(x1, y1, color)
        for i in range(x1 + 1, x2 + 1):
            if P < 0:
                P += A
            else:
                P += B
                y1 += 1 if m > 0 else -1
            set_pixel(i, y1, color)
    elif abs(m) > 1:
        # 统一y轴递增方向
        if y1 > y2:
            x1, x2 = x2, x1
            y1, y2 = y2, y1
            dx = -dx
            dy = -dy
            m = dy / dx  # 更新斜率符号
        
        A = 2 * dx
        B = A - 2 * dy
        P = A - dy
        set_pixel(x1, y1, color)
        for i in range(y1 + 1, y2 + 1):
            if P < 0:
                P += A
            else:
                P += B
                x1 += 1 if m > 0 else -1
            set_pixel(x1, i, color)
    elif abs(m) == 1:
        set_pixel(x1, y1, color)
        for _ in range(x1 + 1, x2 + 1):
            x1 += 1
            y1 += 1 if m == 1 else -1
            set_pixel(x1, y1, color)

修复说明 #

1. 统一y轴方向：在处理|m|>1的分支时，先判断y1是否大于y2，若成立则交换坐标并更新dx、dy和斜率，确保y轴递增，循环可以正常执行
2. 优化变量计算：用dx、dy替代重复的(x2-x1)、(y2-y1)，减少冗余计算
3. 简化条件判断：将if m < 0: y1 -=1 else: y1 +=1简化为y1 += 1 if m >0 else -1，提升代码可读性
4. 修复±1斜率分支：原代码在循环中先绘制点再递增坐标，会导致起始点重复绘制，调整为先递增再绘制（除初始点）

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