I love the Bresenham line algorithm. It’s an old algorithm that’s been around for more than half a century since it was created to drive plotters. One of the cool things about it is that it requires nothing more than addition, subtraction and multiplication * 2 (usually done as a bit shift or an add). Another cool thing is that it lends itself quite nicely to being implemented in F# tail-recursively. I did this as a mental exercise in Rosetta coding to see what it would look like in F# (spoiler: it looks really nice). The reference code I started with was in C and can be found here (PDF), which has a pretty great description of the algorithm and how to optimize the living daylights out of it. The F# code is optimized for reading.
To go into this, I’m going to say that for the algorithm, there are 8 separate cases for 8 octants in the Cartesian plane, but a little planning, you can get this down to 2 octants (one x dominant, the other y dominant), and honestly, the two octants are nearly identical.
Since F# is a functional language, we’re going to solve the inside-out problem, by deferring the work that must be done at each pixel to an external function:
type PixelFunc = int -> int -> unit
which we will call with the (x, y) coordinates of a pixel that should be set. Easy.
Next, here’s internal xdominant octant case:
let Octant0 xdir = let dy2 = dy * 2 let dy2dx2diff = dy2 - (dx * 2) let rec Octant0Rec x y count error = if count = 0 then () else let (y0next, errornext) = if error >= 0 then (y + 1, error + dy2dx2diff) else (y, error + dy2) pf (x + xdir) y0next Octant0Rec (x + xdir) y0next (count - 1) errornext pf x0 y0 Octant0Rec x0 y0 dx (dy2 - dx)
You should be aware that this internal function refers to a couple of variables that are in an outer scope: dx, which is the absolute value of Δx and dy is the absolute value of Δy and x0 and y0 are the starting pixel. Essentially, Octant0Rec will draw count pixels starting from an initial x and y, stepping along x (either positively or negatively) and conditionally staying on the same y or moving when the error gets too big. Octant0 sets up dy times two, and the difference between dx and dx times 2. So simple.
So now that we have that out of context, let’s put it in context with the whole routine:
let DrawLine ix0 iy0 ix1 iy1 (pf:PixelFunc) = let (x0, y0, x1, y1) = if iy0 > iy1 then (ix1, iy1, ix0, iy0) else (ix0, iy0, ix1, iy1) let tdx = x1 - x0 let (dx, xinc) = if tdx < 0 then (-tdx, -1) else (tdx, 1) let dy = y1 - y0 let Octant0 xdir = let dy2 = dy * 2 let dy2dx2diff = dy2 - (dx * 2) let rec Octant0Rec x y count error = if count = 0 then () else let (y0next, errornext) = if error >= 0 then (y + 1, error + dy2dx2diff) else (y, error + dy2) pf (x + xdir) y0next Octant0Rec (x + xdir) y0next (count - 1) errornext pf x0 y0 Octant0Rec x0 y0 dx (dy2 - dx) let Octant1 xdir = let dx2 = dx * 2 let dx2dy2diff = dx2 - (dy * 2) let rec Octant1Rec x y count error = if count = 0 then () else let (x0next, errornext) = if error >= 0 then (x + xdir, error + dx2dy2diff) else (x, error + dx2) pf x0next (y + 1) Octant1Rec x0next (y + 1) (count - 1) errornext pf x0 y0 Octant1Rec x0 y0 dy (dx2 - dy) if dx > dy then Octant0 xinc else Octant1 xinc
The first thing the set up code does is order the initial starting and ending (x,y) coordinates, then calculates the deltas and based on whether x or y is dominant, selects the appropriate octant code.
So we can see that you can implement Bresenham’s line algorithm in a way that is readable, tail-recursive, and uses nothing but immutable variables.