Get All Points Of A Straight Line In Python

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 int

Solution 1:

defget_line(x1, y1, x2, y2):
    points = []
    issteep = abs(y2-y1) > abs(x2-x1)
    if issteep:
        x1, y1 = y1, x1
        x2, y2 = y2, x2
    rev = Falseif 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 = Noneif y1 < y2:
        ystep = 1else:
        ystep = -1for x inrange(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 reversedif rev:
        points.reverse()
    return points

Solution 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)

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

Solution 4:

defgetLine(x1,y1,x2,y2):
    if x1==x2: ## Perfectly horizontal line, can be solved easilyreturn [(x1,i) for i inrange(y1,y2,int(abs(y2-y1)/(y2-y1)))]
    else: ## More of a problem, ratios can be used insteadif 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=0while 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 linereturn line ## Finally, return the line!

Solution 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 reversedif (rev) {
    std::reverse(points.begin(), points.end());
}
return points;
}