Given start and end point, produce a list of points through which line (or ray) will traverse.
Python, 112 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | """
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 _bresenhamlines(start, end, max_iter):
"""
Returns npts lines of length max_iter each. (npts x max_iter x dimension)
>>> s = np.array([[3, 1, 9, 0],[0, 0, 3, 0]])
>>> _bresenhamlines(s, np.zeros(s.shape[1]), max_iter=-1)
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]],
<BLANKLINE>
[[ 0, 0, 2, 0],
[ 0, 0, 1, 0],
[ 0, 0, 0, 0],
[ 0, 0, -1, 0],
[ 0, 0, -2, 0],
[ 0, 0, -3, 0],
[ 0, 0, -4, 0],
[ 0, 0, -5, 0],
[ 0, 0, -6, 0]]])
"""
if max_iter == -1:
max_iter = np.amax(np.amax(np.abs(end - start), axis=1))
npts, dim = start.shape
nslope = _bresenhamline_nslope(end - start)
# steps to iterate on
stepseq = np.arange(1, max_iter + 1)
stepmat = np.tile(stepseq, (dim, 1)).T
# some hacks for broadcasting properly
bline = start[:, np.newaxis, :] + nslope[:, np.newaxis, :] * stepmat
# Approximate to nearest int
return np.array(np.rint(bline), 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. if -1, maximum number of required
points are traversed
Returns:
linevox (n x dimension) A cumulative array of all points traversed by
all the lines so far.
>>> s = np.array([[3, 1, 9, 0],[0, 0, 3, 0]])
>>> bresenhamline(s, np.zeros(s.shape[1]), max_iter=-1)
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],
[ 0, 0, 2, 0],
[ 0, 0, 1, 0],
[ 0, 0, 0, 0],
[ 0, 0, -1, 0],
[ 0, 0, -2, 0],
[ 0, 0, -3, 0],
[ 0, 0, -4, 0],
[ 0, 0, -5, 0],
[ 0, 0, -6, 0]])
"""
# Return the points as a single array
return _bresenhamlines(start, end, max_iter).reshape(-1, start.shape[-1])
if __name__ == "__main__":
import doctest
doctest.testmod()
|
I added this method to pypedia.com: http://www.pypedia.com/index.php/bresenhamline
For an example of usage go here: http://bit.ly/12ynvmD and press the "Run" button.