布雷森汉姆直线算法错误

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 上，它对某些情况返回 nope。
我通过交换点来解决了这个问题，但这显然是一个糟糕的解决方案。 有人可以帮我概括一下算法吗？

- om-nom-nom

---

很遗憾，您的方法会导致“ThrowableException: Java heap space”（这是因为当“hasNext”实际上不应该成为“true”时，它大多数情况下会变成“true”，从而使代码进入无限循环）。 - om-nom-nom

顺便提一下，我在这段代码中发现了另一个 bug -- 在同一点之间的线路（例如 (0,0) -> (0,0)）会导致无限循环。 - om-nom-nom

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都不为零，且它们的符号决定了步骤的方向。

- Kipton Barros

---

非常感谢！@jeela的答案看起来最漂亮且简单（乘法很麻烦），但我除了最后一个点以外都得到了所有分数。您的答案既正确又好。 - om-nom-nom

Answer 2

维基百科代码的相当字面意思是：

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

- Jamil