Bresenham直線算法錯誤

我有bresenham's algorithm下面的代碼，代表適應斯卡拉 Java代碼。Bresenham直線算法錯誤

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它說沒了的情況下，以上）。
我已經處理了交換點，但這顯然是一個不好的解決方案。任何人都可以幫我推廣算法嗎？

來源

2011-08-16 om-nom-nom

試着說||代替＆＆。 –

不幸的是，你的方法會導致'ThrowableException：Java堆空間'（這是因爲'hasNext'通常變爲'true'，實際上不應該和line無窮大）。 –

順便說一句，我發現這段代碼中的另一個bug - 線相同點之間（例如（0,0） - >（0,0））提供了無限循環 –

在故障情況下，你試圖去從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-16 18:49:12

非常感謝！ @jeela答案似乎是最漂亮和容易的（乘法很重），但我得到除了最後一個點以外的所有點。你的答案既正確又好。 –

的維基代碼一個相當直譯是：

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

來源

2011-08-16 19:00:59 Jamil

Bresenham直線算法錯誤

回答

相關問題