Как алгоритм Брезенхэма одновременно отслеживает ошибку 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 является ведущей осью. В этом случае мы просто отслеживаем ошибку y, а когда мы увеличиваем x, мы пропорционально увеличиваем ошибку y. Если оно превышает определенный порог, мы также увеличиваем y и обновляем ошибку соответственно. Используя некоторые простые алгебраические изменения, целое может быть сделано в целочисленной арифметике

Но я просто не могу сделать головы или хвосты этого конкретного кода. Как одна переменная может отслеживать две ошибки одновременно?

Answer 1

Я не уверен, что это правильный способ прояснить вашу стартовую форму.

Код может решить проблемы с разным направлением, сначала решив sx и sy. Другой удобный момент, который он выявляет, это то, что он может нарисовать четыре вида уклона (k) image1-1: разные уклоны в системе координат

как 1-1 показывает, что другие 6 синих линий могут проецироваться на k>1, а 0<=k<=1 жирные синие линии. поэтому в этом случае нам нужно иметь дело только с k>1 и 0<=k<=1.

Теперь посмотрим на формулу о различном значении наклона (k). image1-2: формула о различном значении наклона (k)

• 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)(позиция e2 в координате x) до точки (-3,0)(позиция -dx в координате x) больше расстояния между точкой (0,3)(позиция e2 в координате y) в (0,2)(позиция dy в координате y)

это может означать, что в то время как err -= dy позволяет err уменьшаться каждый раз, не совсем точно, чтобы выразить это: e2 достигает границы по координате y (e2

// 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

• 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 и решаем, пойдем ли мы в первый случай if, чтобы переместить наш x.