python - 对于某些角度的线，我对 Bresenham 算法的实现失败

我已经在 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) 位于显示屏的左上角。

我的测试框架非常简单。这是一个独立的函数，所以我只传递两点:

最佳答案

我不知道你为什么使用 xstep 变量。你真的不需要你正在使用的算法。



您不需要 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 bool 值在需要之前被评估。如果 steep 条件执行，则值会更改，但到那时您的 backward 条件就不同了。要解决此问题，请不要使用 backward bool 值，而是将其设为显式表达式:

if x0 > x1:
    # swapping here

再说一次，由于您稍后最终会使用 bool 值，因此您可以在条件之前定义它:

backward = x0 > x1

if backward:

关于python - 对于某些角度的线，我对 Bresenham 算法的实现失败，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3713821/