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)

Hegumen

What have you tried so far? Do you know how to solve for the equation of a line? Can you not generate points in a range? Where are you stuck? – Wayward

You must compute the slope of the line, reduce it to an irreducible fraction and use numerator/denominator as increments for x and y. – Askins

er... lots of segments will have very few/no points where both k and z are exact integers. Even when you do have integers, some segments will only have a few exact-integer pairs whereas others have many - making the sparseness highly variable. I don't think you've thought out this integer thing fully. – Acme

What you are looking for is a bit unclear to me. Can you give an example output for a few simple inputs. For instance, what should be the output for A = (0, 0) , B = (17, 19) ? – Haycock

(a) do the math and figure out the algorithm you want to implement. (b) try to implement it. (c) Come back here if you have difficulties with the programming. – Schild

Do you mean this? en.m.wikipedia.org/wiki/Bresenham's_line_algorithm – Electroballistics

Actually for the integer problem I would dispense with slope finding and work with common prime factors of the input integers. Clarify if that's really what you mean and I'll try to work it up. – Villein

Answer 1

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

Hegumen

a simple explanation of the answer would have helped instead of just code. – Zook

Answer 2

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)

Carolann

While m can be easily gotten, establishing c might be trivial to the human mind but it get's more complicated having to make exceptions for vertical lines which obviously never intersect with y hence c = ∞ and also special case for horizontal lines where c=y – Hegumen

In these cases, you could add exception where a[0] == b[0] or a[1] == b[1], admittedly not the nicest way of going about it, but fairly trivial – Carolann

Answer 3

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, +).

Colophony

I know the mathematical concept of a straight line and yes, I can write pseudo_code to demonstrate the concept. But as the question reads, am in need of a working function code. Reference my except code above. – Hegumen

Are you that lazy ? You didn't even realize that I did provide Python code. – Colophony

Answer 4

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!

Tauro

Answer 5

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

Eglanteen

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.

Sophistry

That is possibly the worst definition of the straight line I have seen - what is wrong with y=mx+c ? – Baronetage

Well nothing except what i've described is how a line is drawn on screen, what y=mx+c does is describe it geometrically accurate. – Sophistry

Could you rephrase your explanation in a human-readable form ? – Colophony

Yes @Yves Daust is right to complain. Sorry, his answer is mint, my only defence is that i'm trying to describe a visualisation of how the math described in his answer actually looks. – Sophistry