Search code examples
line

Why is my naive line drawing algorithm faster than Bresenham


I implemented both the naive line drawing algorithm and bresenham algorithm. When I run the program with a 1000 lines, the naive line drawing algorithm is faster than the bresenham algorithm. Could anyone explain why? Here is my code for both methods

def simpleLine(x1, y1, x2, y2):
dy = y2-y1;
dx = x2-x1;
x = x1

    m = dy/dx;
    b = y1-m*x1;
    if(x1>x2):
        x1,x2 = x2,x1
    x=x1
    while(x<=x2):
        y=m*x+b;
        PutPixle(win,x,round(y));
        x=x+1

'

def BresenhamLine(x1, y1, x2, y2):

dx = abs(x2 - x1)
dy = abs(y2 - y1)


p = 2 * dy - dx
duady = 2 * dy
duadydx = 2 * (dy - dx)

x = x1
y = y1
xend = x2
if(x1 > x2):
    x, y,xend = x2, y2,x1




while(x < xend):
    PutPixle(win,x,y)
    x =x+1
    if(p<0):


        p = p + 2*dy
    else:

        y = y-1 if y1>y2 else y+1
        p = p+2*(dy-dx)

Solution

  • Bresenham's algorithm was invented for languages and machines with different performance characteristics than your python environment. In particular, low-level languages on systems where floating point math is much more expensive than integer math and branches.

    In Python, your simple version is faster even though it uses floating point and rounding, because Python is slow and it executes fewer python operations per pixel. Any difference in speed between single integer or floating point operations is dwarfed by the cost of just doing python stuff.