Ошибка алгоритма линии Брезенхэма

Question

У меня был следующий код алгоритма Брезенхема , который представляет собой адаптированный к Scala Java-код.

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 должно быть обобщено для обработки в любом направлении. Умный способ был бы,

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

, который работает, потому что sx и sy отличны от нуля, а их знак определяет направление шагов.

Answer 2

Довольно буквальный перевод кода википедии будет:

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