Моя реализация алгоритма Брешенема терпит неудачу для строк под определенными углами

Question

Я написал реализацию алгоритма Брешенема в Python (после 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 

Кто-нибудь видел, что я завинчивание?

---

EDIT:

я добавил печати код функции.

(0,0) находится в верхнем левом углу дисплея.

Моя тестовая структура довольно проста. Это автономная функция, так что я просто передать два очка к нему:

происхождения = (416, 384)
Dest = (440, 347)
Bresenham (происхождение, Dest)
(416, 384)
(440, 347)
x0 = 384
x1 = 347
у0 = 416
у1 = 440
[]

Answer 1

Я не знаю, почему вы используете переменную xstep. Вам не нужен алгоритм, который вы используете.

@Gabe: xstep необходима, потому что без него, если x0> x1, то цикл будет немедленно прекращено, так как шаг по умолчанию для Python для петли 1.

Причина вам не нужна переменная 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 

EDIT: Проблема в том, что backward boolean оценивается до это должно быть. Если выполняется условие steep, значения меняются, но к тому времени ваш backward условный отличается.Чтобы исправить это, вместо того, чтобы использовать 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