Welcome, guest | Sign In | My Account | Store | Cart

Given start and end point, produce a list of points through which line (or ray) will traverse.

Python, 112 lines
 ``` 1 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]], [[ 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() ```

1 comment

Alexandros Kanterakis 11 years, 2 months ago

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.

 Created by Vikas Dhiman on Wed, 25 Apr 2012 (MIT)