Returns a list of points in a line between (x1, y1) and (x2, y2). Uses the Bresenham line algorithm. More info at: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
(x1, y1, x2, y2)
| 119 | |
| 120 | |
| 121 | def line(x1, y1, x2, y2): |
| 122 | """Returns a list of points in a line between (x1, y1) and (x2, y2). |
| 123 | |
| 124 | Uses the Bresenham line algorithm. More info at: |
| 125 | https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm""" |
| 126 | |
| 127 | # Check for the special case where the start and end points are |
| 128 | # certain neighbors, which this function doesn't handle correctly, |
| 129 | # and return a hard coded list instead: |
| 130 | if (x1 == x2 and y1 == y2 + 1) or (y1 == y2 and x1 == x2 + 1): |
| 131 | return [(x1, y1), (x2, y2)] |
| 132 | |
| 133 | points = [] |
| 134 | isSteep = abs(y2 - y1) > abs(x2 - x1) |
| 135 | if isSteep: |
| 136 | x1, y1 = y1, x1 |
| 137 | x2, y2 = y2, x2 |
| 138 | isReversed = x1 > x2 |
| 139 | |
| 140 | if isReversed: |
| 141 | x1, x2 = x2, x1 |
| 142 | y1, y2 = y2, y1 |
| 143 | |
| 144 | deltax = x2 - x1 |
| 145 | deltay = abs(y2 - y1) |
| 146 | error = int(deltax / 2) |
| 147 | y = y2 |
| 148 | ystep = None |
| 149 | if y1 < y2: |
| 150 | ystep = 1 |
| 151 | else: |
| 152 | ystep = -1 |
| 153 | for x in range(x2, x1 - 1, -1): |
| 154 | if isSteep: |
| 155 | points.append((y, x)) |
| 156 | else: |
| 157 | points.append((x, y)) |
| 158 | error -= deltay |
| 159 | if error <= 0: |
| 160 | y -= ystep |
| 161 | error += deltax |
| 162 | else: |
| 163 | deltax = x2 - x1 |
| 164 | deltay = abs(y2 - y1) |
| 165 | error = int(deltax / 2) |
| 166 | y = y1 |
| 167 | ystep = None |
| 168 | if y1 < y2: |
| 169 | ystep = 1 |
| 170 | else: |
| 171 | ystep = -1 |
| 172 | for x in range(x1, x2 + 1): |
| 173 | if isSteep: |
| 174 | points.append((y, x)) |
| 175 | else: |
| 176 | points.append((x, y)) |
| 177 | error -= deltay |
| 178 | if error < 0: |