Bresenham算法如何同时跟踪一个变量中的x和y错误？

Question

请考虑Rosetta Code的这个片段（使用C语言）：

void line(int x0, int y0, int x1, int y1) {

  int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
  int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1; 
  int err = (dx>dy ? dx : -dy)/2, e2;

  for(;;){
    setPixel(x0,y0);
    if (x0==x1 && y0==y1) break;
    e2 = err;
    if (e2 >-dx) { err -= dy; x0 += sx; }
    if (e2 < dy) { err += dx; y0 += sy; }
  }
}

我理解当X是驱动轴时Bresenham算法如何工作。在这种情况下，我们只是跟踪y误差，当我们增加x时，我们按比例增加y误差。如果超过某个阈值，我们也会增加y并相应地更新错误。使用一些简单的代数变化，整体可以用整数运算来完成

但我无法做出这个特定代码的正面或反面。一个变量如何同时跟踪两个错误？

Answer 1

我不确定这是澄清你的问题的正确方法。在那里开始形式。

代码可以通过首先决定sx和sy来解决不同方向的问题。它带来的另一个便利点是它可以绘制四种斜率（k）image1-1: different slope in coordinate system

如1-1所示，其他6条蓝线可以投射在k> 1和0 <= k <= 1粗体蓝线上。所以在这种情况下，我们只需要处理k> 1和0 <= k <= 1的情况。

现在让我们看看关于不同斜率（k）值的公式。 image1-2: formula about different slope(k) value

• 1 .

当0 <= k <= 1且dx> dy时，我们选择err = dx / 2

e2 < dy
e2-dy < 0

  (e2 - dy)/dx
= e2/dx - dy/dx    (∵e2 = dx/2
= (dx/2)/dx - dy/dx
= 1/2 - k
[follow the image1-2 can know that it is exactly the initial value of error term: 0.5 - k]

在这种情况下，e2> -dx怎么样？您可以绘制坐标系来模拟该过程。例如：（0,0） - >（6,2）。开头的错误= 3。点（3,0）（x坐标中e2的位置）与点（-3,0）（x坐标中-dx的位置）之间的距离大于点（0,3）之间的距离（ y坐标中的e2的位置）到（0,2）（y坐标中的dy的位置）

这可能意味着，虽然err - = dy让err每次都减少，但是以一种不精确的方式来说：e2以比（e2 <= -dx）更快的速度击中y坐标（e2 <dy）的边界，所以当错误接近时或者已经在x坐标中击中了边界，你进入if情况（e2 <dy）它让err增加dx。保存下一个循环。

// inside if(e2 > -dx)
err -= dy;
err = err - dy;
err/dx = err/dx - dy/dx;
err/dx = err/dx - k;
//it is exactly: di+1 = di - k

//inside if(e2 < dy)
err += dx;
err/dx = err/dx + dx/dx;
//it is exactly: di+1 = di + 1

因此，每次进入for循环，你进入第一个if情况，当e2 <dy你进入第二个if-case使它di + 1 = di -k + 1并移动你的y。

• 2.

当k> 1即dy> dx时，我们选择err = -dy / 2

e2 > -dx
e2+dx > 0

  (e2 + dx)/dx
= e2/dx + dx/dx    (∵e2 = -dy/2
= (-dy/2)/dx - dx/dx
= -k/2 + 1
[follow the image1-2 can know that it is exactly the initial value of error term: 1 - 0.5k]

其余的就像前一个0 <= k <= 1，除了我们每次进入第二个if-case，并决定我们是否会转到第一个if移动我们的x。