Trace:

en:glossary:l:line_calculation

This shows you the differences between two versions of the page.

— |
en:glossary:l:line_calculation [2020/05/23 08:16] (current) Horst JENS created |
||
---|---|---|---|

Line 1: | Line 1: | ||

+ | ===== Bresenham's Line Algorithm ===== | ||

+ | |||

+ | calculates the tiles connected by a line in a 2D-array: | ||

+ | |||

+ | see also: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm | ||

+ | |||

+ | |||

+ | <code python> | ||

+ | def get_line(start, end): | ||

+ | """Bresenham's Line Algorithm | ||

+ | Produces a list of tuples from start and end | ||

+ | source: http://www.roguebasin.com/index.php?title=Bresenham%27s_Line_Algorithm#Python | ||

+ | see also: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm | ||

+ | |||

+ | #>>> 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 | ||

+ | |||

+ | </code> |

/var/www/horst/thepythongamebook.com/data/pages/en/glossary/l/line_calculation.txt ยท Last modified: 2020/05/23 08:16 by Horst JENS

The content of this wiki is licensed by Horst JENS under Creative-Commons Attribution-Share-alike 4.0 international license (cc-by-sa 4.0)