直达Bresenham

Question

Bresenham有一个著名的绘制线条的算法，维基百科上有一篇很好的文章：http://en.wikipedia.org/wiki/Bresenham's_line_algorithm。

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

给定起点x1、y1、终点x2、y2和一些y (y1 <= y <= y2)，是否可以直接计算y行活动像素的所有x坐标

例如，假设我使用标准的Bresenham方法绘制了一条线：

    oooo               - y1
        ooo
           oooo
               ooo     - y
                  oooo - y2

    |                |
    x1               x2

所以对于这个y，我想要得到一个[x1+11, x1+12, x1+13]序列。

我不确定是否有可能像上面那样修改Bresenham，所以如果结果是不可能的，有没有其他方法可以得到看起来与Bresenham计算的序列完全相同的序列？我不关心它是快还是慢，是否使用浮点数，只要它可以直接求值即可。

提前感谢！

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

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)

打印：

□ □ □ □ □ □ □ □ □ □ □
□ □ ■ □ □ □ □ □ □ □ □
□ □ □ ■ □ □ □ □ □ □ □
□ □ □ □ ■ □ □ □ □ □ □
□ □ □ □ □ ■ ■ □ □ □ □
□ □ □ □ □ □ □ ■ □ □ □
□ □ □ □ □ □ □ □ ■ □ □
□ □ □ □ □ □ □ □ □ ■ □
□ □ □ □ □ □ □ □ □ □ ■

Answer 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执行相同的操作