"""
N-D Bresenham line algo
"""
import numpy as np
def bresenhamline_nslope(slope):
"""
Normalize slope for Bresenham's line algorithm.
>>> s = np.array([[-2, -2, -2, 0]])
>>> bresenhamline_nslope(s)
array([[-1., -1., -1., 0.]])
>>> s = np.array([[0, 0, 0, 0]])
>>> bresenhamline_nslope(s)
array([[ 0., 0., 0., 0.]])
>>> s = np.array([[0, 0, 9, 0]])
>>> bresenhamline_nslope(s)
array([[ 0., 0., 1., 0.]])
"""
scale = np.amax(np.abs(slope), axis=1).reshape(-1, 1)
zeroslope = (scale == 0).all(1)
scale[zeroslope] = np.ones(1)
normalizedslope = np.array(slope, dtype=np.double) / scale
normalizedslope[zeroslope] = np.zeros(slope[0].shape)
return normalizedslope
def bresenhamline_step(start, normalizedslope, err):
"""
Performs a single incremental step according to Bresenham's algorithm.
>>> s = np.array([[4, 4, 4, 0]])
>>> ns = bresenhamline_nslope(np.array([[-2, -2, -2, 0]]))
>>> e = np.zeros((1, 4))
>>> bresenhamline_step(s, ns, e)
(array([[ 3., 3., 3., 0.]]), array([[ 0., 0., 0., 0.]]))
>>> s = np.array([[0, 0, 9, 0]])
>>> ns = bresenhamline_nslope(-1 * s)
>>> e = np.zeros((1, 4))
"""
nextpoint = start + normalizedslope + err
nextvox = np.rint(nextpoint)
err = nextpoint - nextvox
return nextvox, err
def bresenhamline_gen(start, end):
"""
Returns a generator of points from (start, end] by ray tracing a line b/w
the points.
Parameters:
start: An array of start points (number of points x dimension)
end: An end points (1 x dimension)
or An array of end point corresponding to each start point
(number of points x dimension)
Returns:
A generator that returns a point being traversed at each step
corresponding to each start point.
>>> [p for p in bresenhamline_gen(np.array([[3, 1, 3, 0]]), np.zeros(4))]
[array([[2, 1, 2, 0]]), array([[1, 0, 1, 0]]), array([[0, 0, 0, 0]])]
"""
dim = start.shape[1]
err = np.zeros(start.shape)
slope = np.array(end - start, dtype=np.float32)
nslope = bresenhamline_nslope(slope)
cur_vox = start
while (np.sum(nslope != 0)):
cur_vox, err = bresenhamline_step(cur_vox, nslope, err)
# reached end ?
nslope[(np.abs(end - cur_vox) < 1).all(1)] = np.zeros(dim)
yield np.array(cur_vox, dtype=start.dtype)
def bresenhamline(start, end, max_iter=5):
"""
Returns a list of points from (start, end] by ray tracing a line b/w the
points.
Parameters:
start: An array of start points (number of points x dimension)
end: An end points (1 x dimension)
or An array of end point corresponding to each start point
(number of points x dimension)
max_iter: Max points to traverse
Returns:
linevox (n x dimension) A cumulative array of all points traversed by
all the lines so far.
>>> s = np.array([[0, 0, 3, 0]])
>>> bresenhamline(s, np.zeros(s.shape[1]), max_iter=9)
array([[0, 0, 2, 0],
[0, 0, 1, 0],
[0, 0, 0, 0]])
>>> s = np.array([[3, 1, 9, 0]])
>>> bresenhamline(s, np.zeros(s.shape[1]), max_iter=9)
array([[3, 1, 8, 0],
[2, 1, 7, 0],
[2, 1, 6, 0],
[2, 1, 5, 0],
[1, 0, 4, 0],
[1, 0, 3, 0],
[1, 0, 2, 0],
[0, 0, 1, 0],
[0, 0, 0, 0]])
"""
dim = start.shape[1]
linevox = np.zeros((0, dim), dtype=start.dtype)
linegen = bresenhamline_gen(start, end)
try:
for i in range(max_iter):
cur_vox = linegen.next()
linevox = np.vstack((linevox, cur_vox))
except StopIteration:
pass
return np.array(linevox, dtype=start.dtype)
if __name__ == "__main__":
import doctest
doctest.testmod()
