2

Bresenham 有一个众所周知的画线算法，维基百科有很好的关于它的文章：http ://en.wikipedia.org/wiki/Bresenham's_line_algorithm 。

主循环根据需要通过加或减 1 来迭代计算 x 或 y 坐标。

给定 start-point x1、y1、 end-pointx2和y2一些y（y1<= y<= y2），是否可以直接计算xrow 处活动像素的所有坐标y？

例如，假设我使用标准 Bresenham 方法画一条线：

    oooo               - y1
        ooo
           oooo
               ooo     - y
                  oooo - y2

    |                |
    x1               x2

所以为此y我想得到一个[x1+11, x1+12, x1+13].

我不确定是否甚至可以像上面那样修改布雷森汉姆，所以如果事实证明这是不可能的，是否有任何其他方法可以获得看起来与布雷森汉姆计算的序列完全相同的序列？我不在乎它是快还是慢，是否使用浮点数，只要可以直接评估即可。

提前致谢！

编辑：为了能够比较我写了一个简单的参考测试的想法：

def line(x0, y0, x1, y1):
    canvas = [[u'\u25a1'] * (max(x0, x1) + 1) for y in range(max(y0, y1) + 1)]
    dx = abs(x1-x0)
    dy = abs(y1-y0)
    if x0 < x1:
        sx = 1
    else:
        sx = -1
    if y0 < y1:
        sy = 1
    else:
        sy = -1
    err = dx-dy
    while True:
        canvas[y0][x0] = u'\u25a0'
        if x0 == x1 and y0 == y1:
            break
        e2 = 2*err
        if e2 > -dy:
            err = err - dy
            x0 = x0 + sx
        if e2 < dx:
            err = err + dx
            y0 = y0 + sy
    return '\n'.join(' '.join(r) for r in canvas)

打字：

print line(2, 1, 10, 8)

印刷：

□ □ □ □ □ □ □ □ □ □ □
□ □ ■ □ □ □ □ □ □ □ □
□ □ □ ■ □ □ □ □ □ □ □
□ □ □ □ ■ □ □ □ □ □ □
□ □ □ □ □ ■ ■ □ □ □ □
□ □ □ □ □ □ □ ■ □ □ □
□ □ □ □ □ □ □ □ ■ □ □
□ □ □ □ □ □ □ □ □ ■ □
□ □ □ □ □ □ □ □ □ □ ■
4

1 回答 1

1

好的，所以 Bresenham 的算法很有吸引力，因为它使用整数数学（它简化了像素位于整数 x,y 坐标的假设）。

求解整数 y 处某行的像素数的算法将执行以下操作：

count = 1
y_query = your query row
x_intercept = intercept of your line at y_query.
round x_intercept to the nearest integer. 
(x_intercept, y_query) now define a pixel in the row

想法是从这个坐标向左和向右走，看看你是否还在 y_query 行中：

//going left
x_new = x_intercept - 1
y_new = the y intercept for the line given x_new
round y_new to the nearest integer
if (y_new == y_query), add 1 to our count of pixels in this row, else break;

对 x_new = x_intercept + 1 执行相同的操作

于 2013-01-28T02:11:08.623 回答