Finding the coordinates of pixels over a line in an image

Question

I have an image represented as a 2D array. I would like to get the coordinates of pixels over a line from point 1 to point 2.

For example, let's say I have an image with size 5x4 like in the image below. And I have a line from point 1 at coordinates (0, 2) to point 2 at (4, 1). Like the red line on the image below:

So here I would like to get the coordinates of the blue pixels as a list like this: [(0, 2), (1, 2), (2, 2), (2, 1), (3, 1), (4, 1)]

How can I achieve this?

I am using Python and numpy, but actually a solution in any language including pseudo code would be helpful. I can then try to convert it into a numpy solution.

user_2836621 · Answer

You can do this with scikit-image:

from skimage.draw import line

# Get coordinates, r=rows, c=cols of your line
rr, cc = line(0,2,4,1)

print(list(zip(rr,cc)))
[(0, 2), (1, 2), (2, 1), (3, 1), (4, 1)]

The source code to see the implemented algorithm: https://github.com/scikit-image/scikit-image/blob/main/skimage/draw/_draw.pyx#L44

It is an implementation of the Bresenham's line algorithm

user_16930239 · Answer

You can use Bresenham's line algorithm

here is a Python code from geeksforgeeks

def bresenham(x1,y1,x2, y2):
 
    m_new = 2 * (y2 - y1)
    slope_error_new = m_new - (x2 - x1)
 
    y=y1
    for x in range(x1,x2+1):
     
        print("(",x ,",",y ,")
")
 
        # Add slope to increment angle formed
        slope_error_new =slope_error_new + m_new
 
        # Slope error reached limit, time to
        # increment y and update slope error.
        if (slope_error_new >= 0):
            y=y+1
            slope_error_new =slope_error_new - 2 * (x2 - x1)
         
     
 
 
# driver function
if __name__=='__main__':
    x1 = 3
    y1 = 2
    x2 = 15
    y2 = 5
    bresenham(x1, y1, x2, y2)

Finding the coordinates of pixels over a line in an image

2 Answers