Get all points of a straight line in python

Question

Very simply, given a point A(x,y) and another point B(m,n), I need a function that can return in any iterable object a list[k,z] of all points in between.

Am only interested in integer points, so no need for floats.

I need the best possible pythonic way because this 'little' function is going to be heavily run and is the key pillar of a larger system.

EDIT:

@roippi, thanks pointing out the gotcha concerning the integers. From my code below, you can see I try to step across the x axis and get corresponding y, then do the same for y. My set of points will not have any non-discrete co-ordinate point, so for the moment I can afford to overlook that small flaw

import itertools
#Vars
origin = {'x':0, 'y':0}

def slope(origin, target):
    if target['x'] == origin['x']:
        return 0
    else:
        m = (target['y'] - origin['y']) / (target['x'] - origin['x'])
        return m

def line_eqn(origin, target):
    x = origin['x']
    y = origin['y']
    c = -(slope(origin, target)*x - y)
    c = y - (slope(origin, target)*x)
    #return 'y = ' + str(slope(target)) + 'x + ' + str(c)
    m = slope(origin, target)
    return {'m':m, 'c':c}

def get_y(x, slope, c):
    # y = mx + c    
    y = (slope*x) + c
    return y

def get_x(y, slope, c):     
    #x = (y-c)/m
    if slope == 0:
        c = 0   #vertical lines never intersect with y-axis
    if slope == 0:
        slope = 1   #Do NOT divide by zero
    x = (y - c)/slope
    return x

def get_points(origin, target):
    coord_list = []
    #Step along x-axis
    for i in range(origin['x'], target['x']+1):     
        eqn = line_eqn(origin, target)
        y = get_y(i, eqn['m'], eqn['c'])        
        coord_list.append([i, y])

    #Step along y-axis
    for i in range(origin['y'], target['y']+1):
        eqn = line_eqn(origin, target)
        x = get_x(i, eqn['m'], eqn['c'])
        coord_list.append([x, i])

    #return unique list     
    return list(k for k,_ in itertools.groupby(sorted(coord_list)))

origin = {'x':1, 'y':3}
target = {'x':1, 'y':6}

print get_points(origin, target)

Answer 1

Here is a C++ equivalent of user1048839's answer for anyone interested:

std::vector<std::tuple<int, int>> bresenhamsLineGeneration(int x1, int y1, int x2, int y2) {
std::vector<std::tuple<int, int>> points;
bool                              issteep = (abs(y2 - y1) > abs(x2 - x1));
if (issteep) {
    std::swap(x1, y1);
    std::swap(x2, y2);
}
bool rev = false;
if (x1 > x2) {
    std::swap(x1, x2);
    std::swap(y1, y2);
    rev = true;
}
int deltax = x2 - x1;
int deltay = abs(y2 - y1);
int error  = int(deltax / 2);
int y      = y1;
int ystep;
if (y1 < y2) {
    ystep = 1;
} else {
    ystep = -1;
}

for (int x = x1; x < x2 + 1; ++x) {
    if (issteep) {
        std::tuple<int, int> pt = std::make_tuple(y, x);
        points.emplace_back(pt);
    } else {
        std::tuple<int, int> pt = std::make_tuple(x, y);
        points.emplace_back(pt);
    }

    error -= deltay;
    if (error < 0) {
        y += ystep;
        error += deltax;
    }
}
// Reverse the list if the coordinates were reversed
if (rev) {
    std::reverse(points.begin(), points.end());
}
return points;
}

Answer 2

def getLine(x1,y1,x2,y2):
    if x1==x2: ## Perfectly horizontal line, can be solved easily
        return [(x1,i) for i in range(y1,y2,int(abs(y2-y1)/(y2-y1)))]
    else: ## More of a problem, ratios can be used instead
        if x1>x2: ## If the line goes "backwards", flip the positions, to go "forwards" down it.
            x=x1
            x1=x2
            x2=x
            y=y1
            y1=y2
            y2=y
        slope=(y2-y1)/(x2-x1) ## Calculate the slope of the line
        line=[]
        i=0
        while x1+i < x2: ## Keep iterating until the end of the line is reached
            i+=1
            line.append((x1+i,y1+slope*i)) ## Add the next point on the line
        return line ## Finally, return the line!

Answer 3

def get_line(x1, y1, x2, y2):
    points = []
    issteep = abs(y2-y1) > abs(x2-x1)
    if issteep:
        x1, y1 = y1, x1
        x2, y2 = y2, x2
    rev = False
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        rev = True
    deltax = x2 - x1
    deltay = abs(y2-y1)
    error = int(deltax / 2)
    y = y1
    ystep = None
    if y1 < y2:
        ystep = 1
    else:
        ystep = -1
    for x in range(x1, x2 + 1):
        if issteep:
            points.append((y, x))
        else:
            points.append((x, y))
        error -= deltay
        if error < 0:
            y += ystep
            error += deltax
    # Reverse the list if the coordinates were reversed
    if rev:
        points.reverse()
    return points

Answer 4

The Bresenham line segment, or variants thereof is related to the parametric equation

X = X0 + t.Dx
Y = Y0 + t.Dy,

where Dx=X1-X0 and Dy=Y1-Y0, and t is a parameter in [0, 1].

It turns out that this equation can be written for an integer lattice, as

X = X0 + (T.Dx) \ D
Y = Y0 + (T.Dy) \ D,

where \ denotes integer division, D=Max(|Dx|, |Dy|) and t is an integer in range [0, D].

As you can see, depending on which of Dx and Dy is has the largest absolute value and what signs it has, one of the equations can be simplified as X = X0 + T (let us assume for now Dx >= Dy >= 0).

To implement this, you have three options:

• use floating-point numbers for the Y equation, Y = Y0 + T.dy, where dy = Dy/D, preferably rounding the result for better symmetry; as you increment T, update with Y+= dy;

• use a fixed-point representation of the slope, choosing a power of 2 for scaling, let 2^B; set Y' = Y0 << B, Dy' = (Dy << B) \ D; and every time you perform Y'+= D', retrieve Y = Y' >> B.

• use pure integer arithmetic.

In the case of integer arithmetic, you can obtain the rounding effect easily by computing Y0 + (T.Dy + D/2) \ D instead of Y0 + (T.Dy \ D). Indeed, as you divide by D, this is equivalent to Y0 + T.dy + 1/2.

Division is a slow operation. You can trade it for a comparison by means of a simple trick: Y increases by 1 every time T.Dy increases by D. You can maintain a "remainder" variable, equal to (T.Dy) modulo D (or T.Dy + D/2, for rounding), and decrease it by D every time it exceeds D.

Y= Y0
R= 0
for X in range(X0, X1 + 1):
  # Pixel(X, Y)
  R+= Dy
  if R >= D:
    R-= D
    Y+= 1

For a well optimized version, you should consider separately the nine cases corresponding to the combination of signs of Dx and Dy (-, 0, +).

Answer 5

Let's assume you know how to work out the equation of a line, so you have m : your gradient, c : your constant

you also have your 2 points: a and b, with the x-value of a lower than the x-value of b

for x in range(a[0], b[0]):
    y = m*x + c
    if isinstance(y, int) and (x,y) not in [a,b]:
        print (x, y)

Answer 6

I looked into this as a project to learn c. The integer values of a straight line follow this pattern. Major number horizontal, one across one up repeated n times followed by minor number horizontal one across one up. The minor number is one more or less than the major number. The major number is effectively the gradient and the minor number corrects the rounding.