bresenham의 라인 알고리즘 오류

Question

스칼라 Java 코드에 맞게 표현 된 bresenham's algorithm의 다음 코드가 있습니다.

def bresenham(x0: Int, y0: Int, x1: Int, y1: Int) = { 
    import scala.math.abs 

    val dx = abs(x1 - x0) 
    val dy = abs(y1 - y0) 

    val sx = if (x0 < x1) 1 else -1 
    val sy = if (y0 < y1) 1 else -1 

    new Iterator[(Int, Int)] { 
     var (x, y) = (x0, y0) 
     var err = dx - dy 

     def next = { 
     val omitted = (x, y) 
     val e2 = 2 * err 
     if (e2 > -dy) { 
      err -= dy 
      x += sx 
     } 
     if (e2 < dx) { 
      err += dx 
      y += sy 
     } 
     omitted 
     } 

     def hasNext = (x <= x1 && y <= y1) 
    } 
    } 

거의 모든 라인에 대한 모든 잘 간다,하지만 때 나는 위에서 아래로 수직선을 계산하기 위해 노력하고있어 (즉 (0.3) -> (0, 0)) 나는군요 아무것도.
문제가 너무 어렵지 않으므로 라고하는 hasNext에 위의 경우에 해당하는이라고 말하면서 나 자신에 대해 어리 석다.
나는 포인트를 교환하여 그 문제를 해결했지만 분명히 나쁜 해결책입니다. 알고리즘을 일반화하는 데 아무도 도와 줄 수 있습니까?

Answer 1

실패한 경우 y0 = 3에서 y1 = 0으로 이동하려고합니다. 따라서 단계는 음수가됩니다, sy = -1. hasNext에서 계속하기위한 조건은 작성한 내용 (y <= y1)이 아닌 y >= y1에 따라 달라집니다.

hasNext은 어느 방향 으로든 처리 할 수 ​​있도록 일반화되어야합니다. 영리한 방법은 sx 및 sy이 0이고, 자신의 기호 단계의 방향을 결정하기 때문에 작동

def hasNext = (sx*x <= sx*x1 && sy*y <= sy*y1) 

될 것이다.

Answer 2

위키 피 디아 코드 오히려 직역은 다음과 같습니다

def hasNext = (!(x==x1 && y==y1))