Returns a list of points in a line between the given points. Uses the Bresenham line algorithm. More info at: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
(x1, y1, x2, y2)
| 129 | |
| 130 | |
| 131 | def line(x1, y1, x2, y2): |
| 132 | """Returns a list of points in a line between the given points. |
| 133 | |
| 134 | Uses the Bresenham line algorithm. More info at: |
| 135 | https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm""" |
| 136 | |
| 137 | # Check for the special case where the start and end points are |
| 138 | # certain neighbors, which this function doesn't handle correctly, |
| 139 | # and return a hard coded list instead: |
| 140 | if (x1 == x2 and y1 == y2 + 1) or (y1 == y2 and x1 == x2 + 1): |
| 141 | return [(x1, y1), (x2, y2)] |
| 142 | |
| 143 | points = [] # Contains the points of the line. |
| 144 | # "Steep" means the slope of the line is greater than 45 degrees or |
| 145 | # less than -45 degrees: |
| 146 | isSteep = abs(y2 - y1) > abs(x2 - x1) |
| 147 | if isSteep: |
| 148 | # This algorithm only handles non-steep lines, so let's change |
| 149 | # the slope to non-steep and change it back later. |
| 150 | x1, y1 = y1, x1 # Swap x1 and y1 |
| 151 | x2, y2 = y2, x2 # Swap x2 and y2 |
| 152 | isReversed = x1 > x2 # True if the line goes right-to-left. |
| 153 | |
| 154 | if isReversed: # Get the points on the line going right-to-left. |
| 155 | x1, x2 = x2, x1 # Swap x1 and x2 |
| 156 | y1, y2 = y2, y1 # Swap y1 and y2 |
| 157 | |
| 158 | deltax = x2 - x1 |
| 159 | deltay = abs(y2 - y1) |
| 160 | extray = int(deltax / 2) |
| 161 | currenty = y2 |
| 162 | if y1 < y2: |
| 163 | ydirection = 1 |
| 164 | else: |
| 165 | ydirection = -1 |
| 166 | # Calculate the y for every x in this line: |
| 167 | for currentx in range(x2, x1 - 1, -1): |
| 168 | if isSteep: |
| 169 | points.append((currenty, currentx)) |
| 170 | else: |
| 171 | points.append((currentx, currenty)) |
| 172 | extray -= deltay |
| 173 | if extray <= 0: # Only change y once extray <= 0. |
| 174 | currenty -= ydirection |
| 175 | extray += deltax |
| 176 | else: # Get the points on the line going left-to-right. |
| 177 | deltax = x2 - x1 |
| 178 | deltay = abs(y2 - y1) |
| 179 | extray = int(deltax / 2) |
| 180 | currenty = y1 |
| 181 | if y1 < y2: |
| 182 | ydirection = 1 |
| 183 | else: |
| 184 | ydirection = -1 |
| 185 | # Calculate the y for every x in this line: |
| 186 | for currentx in range(x1, x2 + 1): |
| 187 | if isSteep: |
| 188 | points.append((currenty, currentx)) |
no outgoing calls
no test coverage detected