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