대각선 운동이없는 Bresenham 선

Question

수정 된 Bresenham 알고리즘이 있습니까? 한 픽셀에서 다음 픽셀로의 단계가 대각선으로, 수평 또는 수직으로 허용되지 않습니까? 아니면 그 어떤 다른 알고리즘? 올라가고 즉 오른쪽으로 -의 당신이 사분면 I에있어 가정 해 봅시다 -

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

사소한 수정이어야한다 (PHP 선호). 대각선을 그리는 대신에 위로 ... 그리고 나서 오른쪽으로하십시오. 이 같은

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