我实现的Bresenham算法在某些角度下绘制线条失败

Question

我在Python中实现了Bresenham算法（参考了维基百科的文章），整体运行得不错，但在某些角度的直线上出现了问题。所有应该在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)是在显示器的左上角。

我的测试框架很简单。它是一个独立的函数，所以我只需要传入两个点：

origin = (416, 384)
dest = (440, 347)
bresenham(origin, dest)
(416, 384)
(440, 347)
x0 = 384
x1 = 347
y0 = 416
y1 = 440
[]

Answer 1

这是我正在使用的一个实现方式，得益于numba，它比纯Python快得多。

from numba import njit
from typing import Tuple
import numpy as np


@njit
def bresenham_numba(x0, y0, x1, y1, w, h):
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    sx = -1 if x0 > x1 else 1
    sy = -1 if y0 > y1 else 1
    err = dx - dy
    points = [(x0, y0)]
    while x0 != x1 or y0 != y1:
        e2 = err * 2
        if e2 > -dy:
            err -= dy
            x0 += sx
        if e2 < dx:
            err += dx
            y0 += sy
        points.append((x0, y0))

    points = [p for p in points if 0 <= p[0] < h and 0 <= p[1] < w]
    return points


def calculate_bresenham(start_point: Tuple[int, int], end_point: Tuple[int, int], resolution: Tuple[int, int]):
    w, h = resolution
    x0, y0 = start_point
    x1, y1 = end_point
    bresenham_list = bresenham_numba(x0, y0, x1, y1, w, h)
    return np.array(bresenham_list)

Answer 2

backward = x0 > x1 

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

问题在于你在交换 x 和 y 之前就计算了 x0 > x1。

你应该这样做：

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

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

Answer 3

我不太明白你为什么要用一个叫xstep的变量。其实在你用的这个算法里，根本不需要这个变量。

@Gabe: xstep是需要的，因为如果没有它，当x0大于x1时，for循环会立刻结束，因为Python的for循环默认步长是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

编辑: 问题在于backward这个布尔值在需要之前就被计算了。如果steep条件执行了，值就会改变，但到那时你的backward条件已经不同了。要解决这个问题，不如把backward改成一个明确的表达式：

if x0 > x1:
    # swapping here

不过，既然你最后还会用到这个布尔值，你可以在条件之前先定义它：

backward = x0 > x1

if backward: