Bresenham算法的執行失敗，對於某些角度的線條

Question

我已經在Python中編寫了一個Bresenham算法的實現（跟在Wikipedia article之後），並且除了某些角度的線條以外，它正常工作。所有應該在45度和90度之間或者135度和270度之間延伸的線將沿着y = x線延伸。

這裏是我的代碼：

def bresenham(origin, dest): 
    # debug code 
    print origin 
    print dest 
    # end debug code 
    x0 = origin[0]; y0 = origin[1] 
    x1 = dest[0]; y1 = dest[1] 
    steep = abs(y1 - y0) > abs(x1 - x0) 
    backward = x0 > x1 

    if steep: 
     x0, y0 = y0, x0 
     x1, y1 = y1, x1 
    if backward: 
     x0, x1 = x1, x0 
     y0, y1 = y1, y0 

    dx = x1 - x0 
    dy = abs(y1 - y0) 
    error = dx/2 
    y = y0 

    if y0 < y1: ystep = 1 
    else: ystep = -1 

    result = [] 
    #if x0 > x1: xstep = -1 
    #else: xstep = 1 
    # debug code 
    print "x0 = %d" % (x0) 
    print "x1 = %d" % (x1) 
    print "y0 = %d" % (y0) 
    print "y1 = %d" % (y1) 
    for x in range(x0, x1): 
     if steep: result.append((y,x)) 
     else: result.append((x,y)) 
     error -= dy 
     if error < 0: 
      y += ystep 
      error += dx 
    # ensure the line extends from the starting point to the destination 
    # and not vice-versa 
    if backward: result.reverse() 
    print result 
    return result 

任何人看到我搞砸了？

---

編輯：

我添加了一些印刷的代碼的功能。

（0,0）位於顯示屏的左上角。

我的測試框架非常簡單。這是一個獨立的功能，所以我只是通過兩點吧：

起源=（416，384）
DEST =（440，347）
布氏（原產地，DEST）
（416，384）
（440，347）
X0 = 384
X1 = 347
Y0 = 416個
Y1 = 440
[]

Answer 1

我不知道爲什麼你使用的是XSTEP變量。你並不需要使用你正在使用的算法。

@Gabe：需要XSTEP原因無它，如果X0> X1，則for循環將立即終止，作爲一個Python for循環默認的步驟是1

原因你不需要xstep變量是因爲，如果它正在倒退，座標已經被切換（在開始處有條件的if backward:），以便終點現在是起點，反之亦然，這樣我們現在是仍然從左到右。

你只需要這樣：

if backward: return result.reverse() 
else: return result 

：

result = [] 

for x in range(x0, x1): 
    if steep: result.append((y, x)) 
    else: result.append((x, y)) 
    error -= dy 
    if error < 0: 
     y += ystep 
     error += dx 

return result 

如果你想從開始爲終點座標列表中，那麼你就可以在年底做檢查編輯：問題是backward布爾正在評估它需要之前。如果steep條件執行，那麼值會更改，但是到那時您的條件將有所不同。爲了解決這個問題，而不是使用backward布爾值，使之成爲明確表示：

if x0 > x1: 
    # swapping here 

再說，因爲你最終使用布爾以後，你可能只是之前的有條件定義它：

backward = x0 > x1 

if backward: 

Answer 2

問題是你在計算x0 > x1之前換了x和y。

相反的：

backward = x0 > x1 

if steep: 
    x0, y0 = y0, x0 
    x1, y1 = y1, x1 
if backward: 
    x0, x1 = x1, x0 
    y0, y1 = y1, y0 

你應該有：

if steep: 
    x0, y0 = y0, x0 
    x1, y1 = y1, x1 

backward = x0 > x1 
if backward: 
    x0, x1 = x1, x0 
    y0, y1 = y1, y0