简化的 Bresenham 线算法:它*确切*做什么? [英] Simplified Bresenham's line algorithm: What does it *exactly* do?

问题描述

基于维基百科关于 Bresenham 线算法的文章，我实现了那里描述的 简化版，我的Java 实现如下所示:

Based on Wikipedia's article on Bresenham's line algorithm I've implemented the simplified version described there, my Java implementation looks like this:

int dx = Math.abs(x2 - x1);
int dy = Math.abs(y2 - y1);

int sx = (x1 < x2) ? 1 : -1;
int sy = (y1 < y2) ? 1 : -1;

int err = dx - dy;

while (true) {
    framebuffer.setPixel(x1, y1, Vec3.one);

    if (x1 == x2 && y1 == y2) {
        break;
    }

    int e2 = 2 * err;

    if (e2 > -dy) {
        err = err - dy;
        x1 = x1 + sx;
    }

    if (e2 < dx) {
        err = err + dx;
        y1 = y1 + sy;
    }
}

现在我明白 err 控制 x 轴上的步骤与 y 轴上的步骤之间的比率 - 但现在我应该记录代码在做什么我未能清楚地表达它的用途，以及为什么 完全 if 语句是，它们如何，以及为什么 err 以代码中所见的方式改变.

Now I do understand that err controls the ratio between steps on the x-axis compared to steps on the y-axis - but now that I'm supposed to document what the code is doing I fail to clearly express, what it is for, and why exactly the if-statements are, how they are, and why err is changed in the way as seen in the code.

维基百科没有指出任何更详细的解释或来源，所以我想知道:

Wikipedia doesn't point to any more detailled explanations or sources, so I'm wondering:

err 究竟做了什么以及为什么 dx 和 dy 以完全显示的方式使用以保持两者之间的正确比例使用这种简化版的 Bresenham 线算法的水平和垂直步骤?

What precisely does err do and why are dx and dy used in exactly the shown way to maintain the correct ratio between horizontal and vertical steps using this simplified version of Bresenham's line algorithm?

推荐答案

直线有多种形式的方程，最熟悉的一种是y=m*x+b.现在如果 m=dy/dx 和 c = dx*b，则 dx*y = dy*x + c.写f(x) = dy*x - dx*y + c，我们有f(x,y) = 0 iff (x,y) 是给定线上的一个点.

There are various forms of equations for a line, one of the most familiar being y=m*x+b. Now if m=dy/dx and c = dx*b, then dx*y = dy*x + c. Writing f(x) = dy*x - dx*y + c, we have f(x,y) = 0 iff (x,y) is a point on given line.

如果你前进x一个单位，f(x,y)改变dy；如果将 y 前进一个单位，则 f(x,y) 改变 dx.在您的代码中，err 表示线性泛函f(x,y) 的当前值，以及语句序列

If you advance x one unit, f(x,y) changes by dy; if you advance y one unit, f(x,y) changes by dx. In your code, err represents the current value of the linear functional f(x,y), and the statement sequences

    err = err - dy;
    x1 = x1 + sx;

和

    err = err + dx;
    y1 = y1 + sy;

代表前进x或y一个单位(在sx或sy方向)，对函数值.如前所述，对于线上的点，f(x,y) 为零；线一侧的点为正，另一侧的点为负.if 测试确定前进 x 是否会比前进 y 更接近所需的行，反之亦然，或两者兼而有之.

represent advancing x or y one unit (in sx or sy direction), with consequent effect on the function value. As noted before, f(x,y) is zero for points on the line; it is positive for points on one side of the line, and negative for those on the other. The if tests determine whether advancing x will stay closer to the desired line than advancing y, or vice versa, or both.

初始化err = dx - dy;旨在最小化偏移误差；如果你放大你的绘图比例，你会发现你的计算线可能不会以不同的初始化集中在所需的线上.

The initialization err = dx - dy; is designed to minimize offset error; if you blow up your plotting scale, you'll see that your computed line may not be centered on the desired line with different initializations.

这篇关于简化的 Bresenham 线算法:它*确切*做什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！