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

У меня был следующий код алгоритма Брезенхема, который представляет собой адаптированный к 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, что означает нет для приведенного выше случая).
Я справился с этим, поменяв местами точки, но это явно плохое решение. Может ли кто-нибудь помочь мне обобщить алгоритм?


person om-nom-nom    schedule 16.08.2011    source источник
comment
к сожалению, ваш подход приводит к `ThrowableException: пространство кучи Java` (это потому, что hasNext в основном становится true, когда на самом деле этого не должно быть, и строка уходит в бесконечность).   -  person om-nom-nom    schedule 18.08.2011
comment
кстати, я нашел еще одну ошибку в этом коде - линия между одинаковыми точками (например, (0,0) -> (0,0)) дает бесконечный цикл   -  person om-nom-nom    schedule 18.08.2011


Ответы (2)


В случае неудачи вы пытаетесь перейти от y0 = 3 к y1 = 0. Таким образом, шаг будет отрицательным, sy = -1. Тогда условие для продолжения в hasNext должно зависеть от y >= y1, а не от того, что вы написали (y <= y1).

hasNext должен быть обобщен для обработки любого направления. Умный способ был бы,

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

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

person Kipton Barros    schedule 16.08.2011
comment
Большое спасибо! Ответ @jeela кажется самым красивым и простым (умножение тяжелое), но я получаю все баллы, кроме последнего. Ваш ответ и правильный, и прекрасный. - person om-nom-nom; 18.08.2011

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

def hasNext = (!(x==x1 && y==y1))
person Jamil    schedule 16.08.2011