Find Pixels that Line Passes Over-CodePudding

I have the equation of a line in y=ax b form, and a starting point, and I want to find all the pixels this line crosses over/into.

At the moment, I was just stepping the x value a bit, calculating y, truncating to find pixel index and adding it to a list if not already in the list, and continuing until reaching a destination point. Kind of as follows (python/pseudocode):

temp_x = start_x
prev_tested = None
pixel_list = []
while(not at destination):
    temp_y = ... find y from x and line equation
    pixel = (int(temp_y), int(temp_x))

    if pixel is not the same as the prev_pixel:
        pixel_list.append(pixel)

    temp_x  = some_step_value

But this just seems wildly inaccurate and inefficient (No need to tell me that in the answers, I understand this is a bad algo). The step value affects a lot. Too large and I will miss pixels (especially if there is a large slope). Too small and I am just wasting iterations. I figured that I can make my step value proportional to my slope, so that I try to minimize the number of iterations I have to do, while also not skipping over too much. But it is not perfect, still skipping over pixels that the line only barely enters the corner.

I feel like there has to be some kind of way to just absolutely determine which pixels a line is touching, but I have had no look finding anything myself. Is there some resource anyone could point me towards that could help with this?

CodePudding user response：

Your step value should be always 1 . What to step over, however depends on your line being more on the horizontal or more on the vertical (that is "a < 1" or "a > 1". For one, step x on 1, and y will be a fraction of that, and for lines more on vertical, y will step with 1 and x will be a fraction of that.

def draw_line(a, b, start_x, destination):
    result = []
    x = start_x
    y = a * x   b
    result.append((int(x),int(y)))
    while int(x) != destination[0] and int(y) != destination[1]:
        if abs(a) < 1:
            x  = 1 if destination[0] > start_x else -1 
            y  = (1 / a) if a!= 0 else 0
        else:
            y  = 1 if destination[1] > y else -1
            x  = 1 / a
        result.append((int(x), int(y)))

    return result
    # maybe there is some missing corner case for vertical lines.

CodePudding user response：

Dx= X1 - X0
Dy= Y1 - Y0
D= Max(Abs(Dx), Abs(Dy))
for I= 0 to D
  X= X0   I * Dx / D
  Y= Y0   I * Dy / D

works in all cases (except the degenerate D=0).

Technical note:

You can avoid the two divisions. One by the fact that the fraction simplifies to ±1, and the other by computing the quotient and remainder incrementally.