3

私はPythonでブレゼンハムのアルゴリズムの実装を書きました（ウィキペディアの記事に続いて）、そしてそれは特定の角度の線を除いて正しく動作します。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）はディスプレイの左上にあります。

私のテストフレームワークは非常に単純です。これはスタンドアロン関数なので、2つのポイントを渡すだけです。

origin =（416、384）
dest =（440、347）
bresenham（origin、dest）
（ 416、384）（440、347
）
x0 = 384
x1 = 347
y0 = 416
y1 = 440
[]

4

2 に答える 2

4

xstep変数を使用している理由がわかりません。使用しているアルゴリズムでは、実際には必要ありません。

@Gabe：xstepが必要なのは、xstepがないとx0> x1の場合、Pythonのforループのデフォルトのステップが1であるため、forループがすぐに終了するためです。

xstep変数が必要ない理由は、逆方向に移動する場合、座標が（if backward:最初の条件で）既に切り替えられているため、終点が始点になり、その逆も同様になるためです。現在も左から右に進んでいます。

あなたはこれが必要です：

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

開始点から終了点までの順序で座標のリストが必要な場合は、最後にチェックを実行できます。

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

編集：問題は、backwardブール値が必要になる前に評価されていることです。条件が実行されるsteepと、値は変更されますが、それまでにbackward条件は異なります。これを修正するには、backwardブール値を使用する代わりに、明示的な式にします。

if x0 > x1:
    # swapping here

繰り返しになりますが、後でブール値を使用することになりますので、条件付きの前にブール値を定義するだけで済みます。

backward = x0 > x1

if backward:
于 2010-09-15T00:40:47.037 に答える
4

問題は、とx0 > x1を交換する前に計算していることです。xy

それ以外の：

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
于 2010-09-15T01:10:10.910 に答える