如何将Bresenham的线条绘制算法与裁剪一起使用？

Question

当使用Bresenham line drawing algorithm绘制直线时，如果该直线可能不在要写入的位图的边界内，则可以剪裁结果，使其适合要写入的图像的轴对齐边界。

虽然可以先将线剪裁到矩形上，然后画线。这并不理想，因为它通常会给线一个稍微不同的斜度（假设正在使用int协弦）。

既然这是一个如此原始的操作，是否有既定的方法来剪裁线条，同时保持相同的形状？

如果有帮助的话，这里是算法的参考实现——它使用int-coords，在绘制直线时避免int/float转换。

我花了一些时间研究这个：

• 问题在virtual dub的网页上有详细描述
• 艾伦·蒂德曼可能的解决方案
  。。。尽管我需要基于文本实现代码，看看它的工作情况如何
• Bresenham的行生成算法带有内置剪辑
  （1995年发表的论文，找不到整个文档？-PDF是一个没有C代码的页面，看起来像是它的付费页面）

Answer 1

根据库兹明的论文，可以使用Bresenham的算法，并将剪切值考虑在内

为了完整起见，这里是该算法的一个工作版本，一个Python函数，尽管它只使用整数算法，所以可以很容易地移植到其他语言。

def plot_line_v2v2i(
    p1, p2, callback,
    clip_xmin, clip_ymin,
    clip_xmax, clip_ymax,
):
    x1, y1 = p1
    x2, y2 = p2

    del p1, p2

    # Vertical line
    if x1 == x2:
        if x1 < clip_xmin or x1 > clip_xmax:
            return

        if y1 <= y2:
            if y2 < clip_ymin or y1 > clip_ymax:
                return
            y1 = max(y1, clip_ymin)
            y2 = min(y2, clip_ymax)
            for y in range(y1, y2 + 1):
                callback(x1, y)
        else:
            if y1 < clip_ymin or y2 > clip_ymax:
                return
            y2 = max(y2, clip_ymin)
            y1 = min(y1, clip_ymax)
            for y in range(y1, y2 - 1, -1):
                callback(x1, y)
        return

    # Horizontal line
    if y1 == y2:
        if y1 < clip_ymin or y1 > clip_ymax:
            return

        if x1 <= x2:
            if x2 < clip_xmin or x1 > clip_xmax:
                return
            x1 = max(x1, clip_xmin)
            x2 = min(x2, clip_xmax)
            for x in range(x1, x2 + 1):
                callback(x, y1)
        else:
            if x1 < clip_xmin or x2 > clip_xmax:
                return
            x2 = max(x2, clip_xmin)
            x1 = min(x1, clip_xmax)
            for x in range(x1, x2 - 1, -1):
                callback(x, y1)
        return

    # Now simple cases are handled, perform clipping checks.
    if x1 < x2:
        if x1 > clip_xmax or x2 < clip_xmin:
            return
        sign_x = 1
    else:
        if x2 > clip_xmax or x1 < clip_xmin:
            return
        sign_x = -1

        # Invert sign, invert again right before plotting.
        x1 = -x1
        x2 = -x2
        clip_xmin, clip_xmax = -clip_xmax, -clip_xmin

    if y1 < y2:
        if y1 > clip_ymax or y2 < clip_ymin:
            return
        sign_y = 1
    else:
        if y2 > clip_ymax or y1 < clip_ymin:
            return
        sign_y = -1

        # Invert sign, invert again right before plotting.
        y1 = -y1
        y2 = -y2
        clip_ymin, clip_ymax = -clip_ymax, -clip_ymin

    delta_x = x2 - x1
    delta_y = y2 - y1

    delta_x_step = 2 * delta_x
    delta_y_step = 2 * delta_y

    # Plotting values
    x_pos = x1
    y_pos = y1

    if delta_x >= delta_y:
        error = delta_y_step - delta_x
        set_exit = False

        # Line starts below the clip window.
        if y1 < clip_ymin:
            temp = (2 * (clip_ymin - y1) - 1) * delta_x
            msd = temp // delta_y_step
            x_pos += msd

            # Line misses the clip window entirely.
            if x_pos > clip_xmax:
                return

            # Line starts.
            if x_pos >= clip_xmin:
                rem = temp - msd * delta_y_step

                y_pos = clip_ymin
                error -= rem + delta_x

                if rem > 0:
                    x_pos += 1
                    error += delta_y_step
                set_exit = True

        # Line starts left of the clip window.
        if not set_exit and x1 < clip_xmin:
            temp = delta_y_step * (clip_xmin - x1)
            msd = temp // delta_x_step
            y_pos += msd
            rem = temp % delta_x_step

            # Line misses clip window entirely.
            if y_pos > clip_ymax or (y_pos == clip_ymax and rem >= delta_x):
                return

            x_pos = clip_xmin
            error += rem

            if rem >= delta_x:
                y_pos += 1
                error -= delta_x_step

        x_pos_end = x2

        if y2 > clip_ymax:
            temp = delta_x_step * (clip_ymax - y1) + delta_x
            msd = temp // delta_y_step
            x_pos_end = x1 + msd

            if (temp - msd * delta_y_step) == 0:
                x_pos_end -= 1

        x_pos_end = min(x_pos_end, clip_xmax) + 1
        if sign_y == -1:
            y_pos = -y_pos
        if sign_x == -1:
            x_pos = -x_pos
            x_pos_end = -x_pos_end
        delta_x_step -= delta_y_step

        while x_pos != x_pos_end:
            callback(x_pos, y_pos)

            if error >= 0:
                y_pos += sign_y
                error -= delta_x_step
            else:
                error += delta_y_step

            x_pos += sign_x
    else:
        # Line is steep '/' (delta_x < delta_y).
        # Same as previous block of code with swapped x/y axis.

        error = delta_x_step - delta_y
        set_exit = False

        # Line starts left of the clip window.
        if x1 < clip_xmin:
            temp = (2 * (clip_xmin - x1) - 1) * delta_y
            msd = temp // delta_x_step
            y_pos += msd

            # Line misses the clip window entirely.
            if y_pos > clip_ymax:
                return

            # Line starts.
            if y_pos >= clip_ymin:
                rem = temp - msd * delta_x_step

                x_pos = clip_xmin
                error -= rem + delta_y

                if rem > 0:
                    y_pos += 1
                    error += delta_x_step
                set_exit = True

        # Line starts below the clip window.
        if not set_exit and y1 < clip_ymin:
            temp = delta_x_step * (clip_ymin - y1)
            msd = temp // delta_y_step
            x_pos += msd
            rem = temp % delta_y_step

            # Line misses clip window entirely.
            if x_pos > clip_xmax or (x_pos == clip_xmax and rem >= delta_y):
                return

            y_pos = clip_ymin
            error += rem

            if rem >= delta_y:
                x_pos += 1
                error -= delta_y_step

        y_pos_end = y2

        if x2 > clip_xmax:
            temp = delta_y_step * (clip_xmax - x1) + delta_y
            msd = temp // delta_x_step
            y_pos_end = y1 + msd

            if (temp - msd * delta_x_step) == 0:
                y_pos_end -= 1

        y_pos_end = min(y_pos_end, clip_ymax) + 1
        if sign_x == -1:
            x_pos = -x_pos
        if sign_y == -1:
            y_pos = -y_pos
            y_pos_end = -y_pos_end
        delta_y_step -= delta_x_step

        while y_pos != y_pos_end:
            callback(x_pos, y_pos)

            if error >= 0:
                x_pos += sign_x
                error -= delta_y_step
            else:
                error += delta_x_step

            y_pos += sign_y

示例用法：

plot_line_v2v2i(
    # two points
    (10, 2),
    (90, 88),
    # callback
    lambda x, y: print(x, y),
    # xy min
    25, 25,
    # xy max
    75, 75,
)

笔记：

• 剪切最小值/最大值是包含的
  （因此最大值应该是图像宽度-1，图像高度-1）

与本文提供的代码相比，有一些改进：

• 该线将始终按照定义的方向绘制（从p1到p2）
• 线的梯度有时会有细微的差别，因此翻转点、计算线、然后变换回来的旋转会产生稍微不同的结果。这种不对称是由X轴和Y轴上的代码交换造成的，以避免代码重复

有关测试和更多示例用法，请参阅：

• Python存储库
• 铁锈版

Answer 2

让我们重新定义这个问题，这样我们就可以看到Bresenham的算法是如何工作的。。。

假设您正在从（x0，y0）到（x1，y1）绘制一条大致水平的线（方法与大致垂直的相同，但轴已切换）：

整行可以用x表示为y的函数（所有整数）：

y = y0 + round( (x-x0) * (y1-y0) / (x1-x0) )

这精确地描述了绘制整条线时要绘制的每个像素，当您一致地剪裁这条线时，它仍然精确地描述了要绘制的每个像素——您只需将其应用于较小的x值范围。

通过分别计算除数和余数，我们可以使用全整数数学来计算这个函数。对于x1

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
    rem-=dx;
    y+=1;
}

Bresenham的算法是一种只是一种快速的方法，可以在您更新x时逐步更新此公式的结果。

下面是我们如何利用增量更新来绘制同一条线从x=xs到x=xe的部分：

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

x=xs;
rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
    rem-=dx;
    y+=1;
}
paint(x,y);
while(x < xe)
{
    x+=1;
    rem+=dy;
    if (rem >= remlimit)
    {
        rem-=dx;
        y+=1;
    }
    paint(x,y);
}

如果您想将余数与0进行比较，您可以在开始时将其抵消：

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

x=xs;
rem = ( (x-x0) * dy % dx ) - remlimit;
y = y0 + (x-x0) * dy / dx;
if (rem >= 0)
{
    rem-=dx;
    y+=1;
}
paint(x,y);
while(x < xe)
{
    x+=1;
    rem+=dy;
    if (rem >= 0)
    {
        rem-=dx;
        y+=1;
    }
    paint(x,y);
}