bresenham python

1def get_line(start, end):
2    """Bresenham's Line Algorithm
3    Produces a list of tuples from start and end
4 
5    >>> points1 = get_line((0, 0), (3, 4))
6    >>> points2 = get_line((3, 4), (0, 0))
7    >>> assert(set(points1) == set(points2))
8    >>> print points1
9    [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
10    >>> print points2
11    [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
12    """
13    # Setup initial conditions
14    x1, y1 = start
15    x2, y2 = end
16    dx = x2 - x1
17    dy = y2 - y1
18 
19    # Determine how steep the line is
20    is_steep = abs(dy) > abs(dx)
21 
22    # Rotate line
23    if is_steep:
24        x1, y1 = y1, x1
25        x2, y2 = y2, x2
26 
27    # Swap start and end points if necessary and store swap state
28    swapped = False
29    if x1 > x2:
30        x1, x2 = x2, x1
31        y1, y2 = y2, y1
32        swapped = True
33 
34    # Recalculate differentials
35    dx = x2 - x1
36    dy = y2 - y1
37 
38    # Calculate error
39    error = int(dx / 2.0)
40    ystep = 1 if y1 < y2 else -1
41 
42    # Iterate over bounding box generating points between start and end
43    y = y1
44    points = []
45    for x in range(x1, x2 + 1):
46        coord = (y, x) if is_steep else (x, y)
47        points.append(coord)
48        error -= abs(dy)
49        if error < 0:
50            y += ystep
51            error += dx
52 
53    # Reverse the list if the coordinates were swapped
54    if swapped:
55        points.reverse()
56    return points

1# https://newbedev.com/python-bresenham-s-line-drawing-algorithm-python-code-example
2# :)
3def bresenham(start: tuple, end: tuple):
4    """Bresenham's Line Algorithm
5    Produces a list of tuples from start and end
6 
7    >>> points1 = get_line((0, 0), (3, 4))
8    >>> points2 = get_line((3, 4), (0, 0))
9    >>> assert(set(points1) == set(points2))
10    >>> print points1
11    [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
12    >>> print points2
13    [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
14    """
15    # Setup initial conditions
16    x1, y1 = start
17    x2, y2 = end
18    dx = x2 - x1
19    dy = y2 - y1
20 
21    # Determine how steep the line is
22    is_steep = abs(dy) > abs(dx)
23 
24    # Rotate line
25    if is_steep:
26        x1, y1 = y1, x1
27        x2, y2 = y2, x2
28 
29    # Swap start and end points if necessary and store swap state
30    swapped = False
31    if x1 > x2:
32        x1, x2 = x2, x1
33        y1, y2 = y2, y1
34        swapped = True
35 
36    # Recalculate differentials
37    dx = x2 - x1
38    dy = y2 - y1
39 
40    # Calculate error
41    error = int(dx / 2.0)
42    ystep = 1 if y1 < y2 else -1
43 
44    # Iterate over bounding box generating points between start and end
45    y = y1
46    points = []
47    for x in range(x1, x2 + 1):
48        coord = (y, x) if is_steep else (x, y)
49        points.append(coord)
50        error -= abs(dy)
51        if error < 0:
52            y += ystep
53            error += dx
54 
55    # Reverse the list if the coordinates were swapped
56    if swapped:
57        points.reverse()
58    return points