Bresenham line doesn't terminate

2019-06-04 05:57发布

I've implemented the Bresenham algorithm from Wikipedia in python but for some lines it doesn't work, like from 1,0 to 0,1 it doesn't stop and keeps going on to make a super long line

def line(x0, y0, x1, y1):
    dx = x1 - x0
    dy = y1 - y0
    sx = x0 < x1 and 1 or -1
    sy = y0 < y1 and 1 or -1
    err = dx - dy

    points = []
    x, y = x0, y0
    while True:
        points += [(x, y)]
        if x == x1 and y == y1:
            break
        e2 = err * 2
        if e2 > -dy:
            err -= dy
            x += sx
        if e2 < dx:
            err += dx
            y += sy
    return points

2条回答
孤傲高冷的网名
2楼-- · 2019-06-04 06:42

You have a type in "if e2 > -dy:". The minus sign is wrong.

查看更多
够拽才男人
3楼-- · 2019-06-04 06:55

You are missing the call to abs in the initialization of dx and dy:

dx = abs(x1 - x0)
dy = abs(y1 - y0)
查看更多
登录 后发表回答