I implemented the pseudocode from wikipedia for Bresenham's algorithm and got a result like this:
0 1 2 3 4 5 6 7 8 9 10
0 0 0 . . . . . . . . .
1 . . 0 . . . . . . . .
2 . . . 0 . . . . . . .
3 . . . . 0 . . . . . .
4 . . . . . 0 . . . . .
5 . . . . . . . . . . 0
6 . . . . . . . . . . .
7 . . . . . . . . . . .
8 . . . . . . . . . . .
9 . . . . . . . . . . .
10 . . . . . . . . . . .
As you can see the algorithm falls apart when dy > dx
. It also is not tracing the line very well from (0,0) to (5,10). I implemented my own algorithm that plugs values into y=mx+b
,rounds the result and uses that to modify the grid.
Python 2.7 code:
def get_grid_cells_btw2(p1,p2):
x1,y1 = p1
x2,y2 = p2
dx = x2-x1
dy = y2-y1
if dx == 0: # will divide by dx later, this will cause err. Catch this case up here
step = int(copysign(1,dy))
pts =[]
for y in range(0,dy,step):
pts.append((x1,y))
return pts
m = dy/(dx+0.0)
b = y1 - m * x1
points = {}
step = 1.0/(max(abs(dx),abs(dy)))
steps = [x * step for x in range(int(x1 / step), int(x2/step + copysign(1,x2)), int(copysign(1,dx)))]
for x in steps:
y = m * x + b
pt = (int(round(x)),int(round(y)))
points["%d,%x"%pt] = pt #catch duplicates
return points.values()
And a much simpler+faster version using Numpy
#function COPIED from stack overflow - https://stackoverflow.com/questions/31097247/remove-duplicate-rows-of-a-numpy-array
def remove_np_duplicates(data):
# Perform lex sort and get sorted data
sorted_idx = np.lexsort(data.T)
sorted_data = data[sorted_idx,:]
# Get unique row mask
row_mask = np.append([True],np.any(np.diff(sorted_data,axis=0),1))
# Get unique rows
out = sorted_data[row_mask]
return out
def get_grid_cells_btw(p1,p2):
x1,y1 = p1
x2,y2 = p2
dx = x2-x1
dy = y2-y1
if dx == 0: # will divide by dx later, this will cause err. Catch this case up here
step = np.sign(dy)
ys = np.arange(0,dy+step,step)
xs = np.repeat(x1, ys.shape[0])
else:
m = dy/(dx+0.0)
b = y1 - m * x1
step = 1.0/(max(abs(dx),abs(dy)))
xs = np.arange(x1, x2, step * np.sign(x2-x1))
ys = xs * m + b
xs = np.rint(xs)
ys = np.rint(ys)
pts = np.column_stack((xs,ys))
pts = remove_np_duplicates(pts)
return pts.astype(int)
And run it with
from pandas import *
cells = get_grid_cells_btw2((0,0),(5,10))
grid = [['.' for row in range(11)] for col in range(11)]
for pt in cells:
x,y=pt
grid[x][y] = '0'
print(DataFrame(grid))
We get
0 1 2 3 4 5 6 7 8 9 10
0 0 0 . . . . . . . . .
1 . 0 0 0 . . . . . . .
2 . . . 0 0 0 . . . . .
3 . . . . . 0 0 0 . . .
4 . . . . . . . 0 0 0 .
5 . . . . . . . . . 0 0
6 . . . . . . . . . . .
7 . . . . . . . . . . .
8 . . . . . . . . . . .
9 . . . . . . . . . . .
10 . . . . . . . . . . .
to (2,10)
0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 . . . . . . . .
1 . . . 0 0 0 0 0 . . .
2 . . . . . . . . 0 0 0
3 . . . . . . . . . . .
4 . . . . . . . . . . .
5 . . . . . . . . . . .
6 . . . . . . . . . . .
7 . . . . . . . . . . .
8 . . . . . . . . . . .
9 . . . . . . . . . . .
10 . . . . . . . . . . .
to (10,6)
0 1 2 3 4 5 6 7 8 9 10
0 0 . . . . . . . . . .
1 0 0 . . . . . . . . .
2 . 0 . . . . . . . . .
3 . . 0 . . . . . . . .
4 . . 0 0 . . . . . . .
5 . . . 0 . . . . . . .
6 . . . 0 0 . . . . . .
7 . . . . 0 . . . . . .
8 . . . . . 0 . . . . .
9 . . . . . 0 0 . . . .
10 . . . . . . 0 . . . .
to (10,10)
0 1 2 3 4 5 6 7 8 9 10
0 0 . . . . . . . . . .
1 . 0 . . . . . . . . .
2 . . 0 . . . . . . . .
3 . . . 0 . . . . . . .
4 . . . . 0 . . . . . .
5 . . . . . 0 . . . . .
6 . . . . . . 0 . . . .
7 . . . . . . . 0 . . .
8 . . . . . . . . 0 . .
9 . . . . . . . . . 0 .
10 . . . . . . . . . . 0