CODEWITHSUNDEEP
pythonalgorithmimage-processinggeometry
SeismicSandwhich
SeismicSandwhich

Reputation: 65

Find Pixels that Line Passes Over

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?

Upvotes: 2

Views: 2081

Answers (3)

Sheradil
Sheradil

Reputation: 477

Skimage has a function that solves this problem. From the documentation (https://scikit-image.org/docs/stable/api/skimage.draw.html#skimage.draw.line):

from skimage.draw import line
img = np.zeros((10, 10), dtype=np.uint8)
rr, cc = line(1, 1, 8, 8)

# When the coordinates are stored in an array
line_in_img = [x1, y1, x2, y2]
rr, cc = line(*line_in_img)
# If you want a list of tuples that contain the coordinates instead of 2 lists that hold the xs and ys
coordinates = list(zip(rr, cc))

coordinates then is a list of coordinate pairs

Upvotes: 1

user1196549
user1196549

Reputation: 

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) to join (X0, Y0) to (X1, Y1) using integer coordinates.

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.

If you believe that this is not accurate enough, you can scale all coordinates by an arbitrary integer M, compute the points with step M and divide the coordinates by M.

Upvotes: 1

jsbueno
jsbueno

Reputation: 110696

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.

Upvotes: 0

Related Questions