Created
May 23, 2019 05:50
-
-
Save Siyeong-Lee/fdacece959c6973603dbda955e45637b to your computer and use it in GitHub Desktop.
Bresenham's Line Algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def get_line(start, end): | |
| """Bresenham's Line Algorithm | |
| Produces a list of tuples from start and end | |
| >>> points1 = get_line((0, 0), (3, 4)) | |
| >>> points2 = get_line((3, 4), (0, 0)) | |
| >>> assert(set(points1) == set(points2)) | |
| >>> print points1 | |
| [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)] | |
| >>> print points2 | |
| [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)] | |
| """ | |
| # Setup initial conditions | |
| x1, y1 = start | |
| x2, y2 = end | |
| dx = x2 - x1 | |
| dy = y2 - y1 | |
| # Determine how steep the line is | |
| is_steep = abs(dy) > abs(dx) | |
| # Rotate line | |
| if is_steep: | |
| x1, y1 = y1, x1 | |
| x2, y2 = y2, x2 | |
| # Swap start and end points if necessary and store swap state | |
| swapped = False | |
| if x1 > x2: | |
| x1, x2 = x2, x1 | |
| y1, y2 = y2, y1 | |
| swapped = True | |
| # Recalculate differentials | |
| dx = x2 - x1 | |
| dy = y2 - y1 | |
| # Calculate error | |
| error = int(dx / 2.0) | |
| ystep = 1 if y1 < y2 else -1 | |
| # Iterate over bounding box generating points between start and end | |
| y = y1 | |
| points = [] | |
| for x in range(x1, x2 + 1): | |
| coord = (y, x) if is_steep else (x, y) | |
| points.append(coord) | |
| error -= abs(dy) | |
| if error < 0: | |
| y += ystep | |
| error += dx | |
| # Reverse the list if the coordinates were swapped | |
| if swapped: | |
| points.reverse() | |
| return points |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment