Линии Bresenham без диагонального движения

Question

Есть ли модифицированный алгоритм Брешенема, где шаг от одного пикселя до следующего не разрешен по диагонали, только по горизонтали или по вертикали? Или любой другой алгоритм, который это делает? (PHP предпочтительное)

Right: 
0 0 0 1 
0 0 1 1 
0 1 1 0 
1 1 0 0 

Wrong: 
0 0 0 1 
0 0 1 0 
0 1 0 0 
1 0 0 0 

Answer 1

Должен быть тривиальной модификацией - скажем, вы находитесь в квадранте I - то есть идет вверх и вправо. Вместо того, чтобы делать диагональ, сделайте вверх ... и затем правую.

Вместо:

for x from x0 to x1 
      plot(x,y) 
      error := error + deltaerr 
      if error ≥ 0.5 then 
       y := y + 1 
       error := error - 1.0 

Что-то вроде этого:

for x from x0 to x1 
     plot(x,y) 
     error := error + deltaerr 
     if error ≥ 0.5 then 
      y := y + 1 
      plot(x,y) 
      error := error - 1.0 

Answer 2

ответ Джеймса довольно прохладно, но, как он отметил, что перекосы линию немного. Другая простая модификация оригинального Bresenham рисует линию без диагональных шагов, которая ближе к «реальной» линии.

Это реализация оригинального алгоритма Bresenham:

public void line(int x0, int y0, int x1, int y1, int value) { 
    int xDist = Math.abs(x1 - x0); 
    int yDist = -Math.abs(y1 - y0); 
    int xStep = (x0 < x1 ? +1 : -1); 
    int yStep = (y0 < y1 ? +1 : -1); 
    int error = xDist + yDist; 

    plot(x0, y0, value); 

    while (x0 != x1 || y0 != y1) { 
     if (2*error > yDist) { 
      // horizontal step 
      error += yDist; 
      x0 += xStep; 
     } 

     if (2*error < xDist) { 
      // vertical step 
      error += xDist; 
      y0 += yStep; 
     } 

     plot(x0, y0, value); 
    } 
} 

Модификация просто сделать либо горизонтальную или вертикальную ступеньку, а не оба, в зависимости от того, индикатор ошибки ближе к горизонтальной или вертикальный шаг:

public void lineNoDiag(int x0, int y0, int x1, int y1, int value) { 
    int xDist = Math.abs(x1 - x0); 
    int yDist = -Math.abs(y1 - y0); 
    int xStep = (x0 < x1 ? +1 : -1); 
    int yStep = (y0 < y1 ? +1 : -1); 
    int error = xDist + yDist; 

    plot(x0, y0, value); 

    while (x0 != x1 || y0 != y1) { 
     if (2*error - yDist > xDist - 2*error) { 
      // horizontal step 
      error += yDist; 
      x0 += xStep; 
     } else { 
      // vertical step 
      error += xDist; 
      y0 += yStep; 
     } 

     plot(x0, y0, value); 
    } 
} 

Это эффективно выбирает тип шага, который сводит к минимуму ошибки, что приводит к линии, которая находится ближе к реальной линии.

Код на Java, но он должен быть легко переносимым на PHP. Я не тестировал его полностью, но он должен работать так же хорошо, как оригинальный Bresenham. Это может быть даже немного быстрее.

Answer 3

Я обнаружил, что ответ Франца Д создает линии, которые не соответствуют оригиналу, когда они близки к горизонтали или вертикали. Хотя функция ниже не идеальна, я обнаружил, что она дает более приятные результаты.

Function BresenhamLineNew : Void(x0 : Int, y0 : Int, x1 : Int, y1 : Int) 

    Local dx : Int = Abs(x1 - x0) 
    Local dy : Int = Abs(y1 - y0) 

    Local sx : Int = -1 
    Local sy : Int = -1 

    If x0 < x1 Then sx = 1 
    If y0 < y1 Then sy = 1 

    Local err : Int = dx - dy 
    Local e2 : Int 

    While True 

     DrawRect x0, y0, 1, 1 

     If x0 = x1 And y0 = y1 Then Exit 

     e2 = 2 * err 

     If dy > dx 
      If e2 > -dy 
       err = err - dy 
       x0 = x0 + sx 
      Elseif e2 < dx 
       err = err + dx 
       y0 = y0 + sy 
      Endif 
     Else 
      If e2 < dx 
       err = err + dx 
       y0 = y0 + sy 
      Elseif e2 > -dy 
       err = err - dy 
       x0 = x0 + sx 
      Endif 
     Endif 

    Wend 

End Function