3

我有以下bresenham 算法的代码，它表示适应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的案例说不）。 我已经通过交换积分来解决这个问题，但这显然是一个糟糕的解决方案。有人可以帮我概括算法吗？

4

2 回答 2

4

在失败的情况下，你试图从y0 = 3到y1 = 0。所以步长为负，sy = -1。那么继续的条件hasNext应该取决于y >= y1而不是你写的（y <= y1）。

hasNext必须泛化以处理任一方向。一个聪明的方法是，

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

之所以有效，是因为sx和sy是非零的，并且它们的符号决定了步骤的方向。

于 2011-08-16T18:49:12.063 回答
2

维基百科代码的相当直译是：

def hasNext = (!(x==x1 && y==y1))
于 2011-08-16T19:00:59.470 回答