Bressenham's line algorithm on rectangular grids

Introduction

Suppose you want to draw a straight line using a grid of pixels. I say "suppose"; of course, almost all of my friends and acquaintances do so daily[1]. I'm now going to describe a classic method to get it straight in my mind. (Most techie friends likely know this already, and those who've done any graphics programming a lot more, but this is a necessary precursor to the sequel on hex grids.)

Part I

( Read more... )

cf. http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

The sequel: Bressenham's line algorithm on hexagonal grids

Assume we are drawing down and to the right again, and that our grid is numbered thusly:

 0 1 2 3 4
  1 # X #
   2 # # #
    3 # # #

The numbers along the top represent the x coordinates. The numbers along the left represent the y-coordinates. Notice that it's not symmetric any more. All the numbers down the left have coordinates x=0, but in real life, are further across. However, this does let us number each hex in a nice, easy, systematic way.

A hex down-and-to-the-right is offset by (+0,+1). A hex down-and-to-the-left is offset by (-1,+1). Fixing up this algorithm to work in any direction will be a bit more fiddly, and I won't bore you with it.

For now we'll assume that our line is from (0,0) to the right and down, and further right than it is down. Eg. from (0,0) to (2,1) or to (4,1).

( Read more... )