Bresenham lines w/o對角線移動

Question

是否有修改的Bresenham算法，其中從一個像素到另一個像素的步驟不允許是對角線，只是水平或垂直？還是其他的算法呢？ （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

我發現Franz D的答案在接近水平或垂直時會產生與原稿不吻合的線條。雖然下面的功能並不完美，但我發現它會產生更好的結果。

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