Direct Bresenham

Question

There is this well known algorithm for drawing lines by Bresenham, Wikipedia has very good article about it: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm.

The main loop iteratively calculates x or y coordinates by adding or subtracting 1 as needed.

Given start-point x1, y1, end-point x2, y2 and some y (y1 <= y <= y2), is it possible to directly calculate all the x coordinates of active pixels at row y?

For example, imagine I draw a line using standard Bresenham method:

    oooo               - y1
        ooo
           oooo
               ooo     - y
                  oooo - y2

    |                |
    x1               x2

So for that y I would like to get a sequence of [x1+11, x1+12, x1+13].

I'm not sure if it is even possible to modify Bresenham as above so if it turns out it is not possible, is there any other way for getting the sequence which looks exactly the same as if it was calculated by Bresenham? I don't care whether it is fast or slow, if it uses floats or not, as long as it can be evaluated directly.

Thanks in advance!

Edit: to be able to compare the ideas I wrote a simple reference test:

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)

Typing:

print line(2, 1, 10, 8)

prints:

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

If you're not concerned about efficiency, you could always create a empty list, and run the algorithm, adding x to that list on every iteration when you're on the wanted y — loopbackbee
@EcirHana: If you know something about the size of your 'pixel', then you can compute the x distance the line traverses between y+(0.5*pixel_size) and y-(0.5*pixel_size), and then divide that distance by the size of the 'pixel' (assuming square pixels). — AndyG
@SauceMaster thanks! And sorry but I don't understand the last part of the sentence about x' and x''? And what about round that 0.5s? Since pixel is 1 "unit" wide. — Ecir Hana
@EricHana, there has to be some resolution at which one stops. That is, in an ideal display, pixels would be infinitesimally small, approaching 0 in area. In such an ideal system we could perfectly draw our line, and at any y coordinate there would only be 1 x intercept! (minus horizontal lines, people!) In the general application of Bresenham's line algorithm, it's applied to some grid of finite size, where a line may have multiple x intercepts for any y-coordinate, directly related to how large a cell of the grid is. My comment above addressed this grid scenario. — AndyG

AndyG AndyG · Accepted Answer · 2013-01-28T02:11:08

Okay, so the Bresenham's algorithm is attractive because it uses integer math (it makes the simplifying assumption that pixels are located at integer x,y coordinates).

An algorithm to solve the number of pixels for some row at an integer y would do something like this:

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

The idea is to go left and right from this coordinate and see if you are still in the y_query row:

//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;

Do the same for x_new = x_intercept + 1

Direct Bresenham

1 Answers