Databases
StackOverflow2013
Postsdbo
POMy implementation of Bresenham's algorithm fails for lines at certain angles
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMy implementation of Bresenham's algorithm fails for lines at certain angles
    primarykey
    data
    text
    <p>I've written an implementation of Bresenham's algorithm in Python (following the <a href="http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm" rel="nofollow noreferrer">Wikipedia article</a>), and it works correctly except for lines at certain angles. All lines that should extend between 45 and 90 degrees, or between 135 and 270 degrees, will instead extend along the line y = x. </p> <p>Here's my code:</p> <pre><code>def bresenham(origin, dest): # debug code print origin print dest # end debug code x0 = origin[0]; y0 = origin[1] x1 = dest[0]; y1 = dest[1] steep = abs(y1 - y0) &gt; abs(x1 - x0) backward = x0 &gt; x1 if steep: x0, y0 = y0, x0 x1, y1 = y1, x1 if backward: x0, x1 = x1, x0 y0, y1 = y1, y0 dx = x1 - x0 dy = abs(y1 - y0) error = dx / 2 y = y0 if y0 &lt; y1: ystep = 1 else: ystep = -1 result = [] #if x0 &gt; x1: xstep = -1 #else: xstep = 1 # debug code print "x0 = %d" % (x0) print "x1 = %d" % (x1) print "y0 = %d" % (y0) print "y1 = %d" % (y1) for x in range(x0, x1): if steep: result.append((y,x)) else: result.append((x,y)) error -= dy if error &lt; 0: y += ystep error += dx # ensure the line extends from the starting point to the destination # and not vice-versa if backward: result.reverse() print result return result </code></pre> <p>Anyone see what I'm screwing up?</p> <hr> <p>EDIT:</p> <p>I added some printing code to the function.</p> <p>(0,0) is at the top left of the display.</p> <p>My test framework is pretty simple. It's a standalone function, so I just pass two points to it:</p> <blockquote> <blockquote> <blockquote> <p>origin = (416, 384)<br> dest = (440, 347)<br> bresenham(origin, dest)<br> (416, 384)<br> (440, 347)<br> x0 = 384<br> x1 = 347<br> y0 = 416<br> y1 = 440<br> []</p> </blockquote> </blockquote> </blockquote>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMax
    1. USMax
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMy implementation of Bresenham's algorithm fails for lines at certain angles
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POMy implementation of Bresenham's algorithm fails for lines at certain angles
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POMy implementation of Bresenham's algorithm fails for lines at certain angles
      1. USgonzobrains
      1. VTFavorite
    1. CO@aaa carp: Nope. Thanks for the answer, though.
      singulars
      1. POMy implementation of Bresenham's algorithm fails for lines at certain angles
      1. USMax
    2. COAside from `if x0 > x1: xstep = -1` being unnecessary, I don't see anything wrong with your code, so your problem is likely to be elsewhere. You'll need to post your actual results so we can see what's happening.
      singulars
      1. POMy implementation of Bresenham's algorithm fails for lines at certain angles
      1. USGabe
    3. CO@Gabe: `xstep` is needed because without it, if `x0 > x1`, then the for loop will terminate immediately, as the default step for a Python for loop is 1. Aside from that, what kind of results do you want? When it goes wrong, it returns a list of points where each point is (1,1) above or below what came before it.
      singulars
      1. POMy implementation of Bresenham's algorithm fails for lines at certain angles
      1. USMax
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload