Computers do simple tasks quickly and reliably. Complex tasks have to be broken down into simple tasks. Even drawing a straight line on the screen is a complex task which must be broken down into simple instructions, telling the computer to paint some dots (picture elements, or pixels) on the screen. We describe two ways of drawing a line, two algorithms.
If you look closely at the screen, you'll see that it is made up of a grid of small dots, called pixels (picture elements). There are about half a million pixels on a typical screen. The computer must be told what colour to use for each pixel, to create each image you see.
Some images, such as photos, are stored as gif (Graphics Interchange Format) files, which store the colour of each pixel in the image. For images that can be represented as line drawings, it takes much less space to store a list of lines, and then compute which pixels should be coloured in each time we want to display the image. Drawing lines is the subject of this note.
The pixels in a picture are arranged in rows and columns. We number the columns from left to right, starting with column zero at the left edge of the picture, and the rows from top to bottom, starting from zero at the top of the picture. So any pixel is described by two numbers, x,y, telling us where in the picture the pixel lies; x giving the column, and y giving the row.
We call the pair of numbers, x,y, the coordinates of the pixel. In the demonstration applet below, we give a view magnified 10x, so a single pixel is represent by 100 actual pixels on the screen. Click on the yellow, diagram area of the applet below; the coordinates of the pixel you click on should appear in the message area.
A line can be described by giving two pixels, saying where the line should start and end. When you click on the diagram, a magnified point is drawn. When you click again, on another point, a line is drawn between the two points. How do we decide which pixels to draw to form the line? We describe two ways: recursive subdivision, and Bresenham's algorithm. You can see both in action by using the buttons to choose an algorithm, and then clicking in the yellow area to select the two ends of the line.
Very short lines, one or two pixels long, are easy to draw: if the line starts and ends at the same pixel, then we just draw that pixel; if the start and end are adjacent pixels, then we just draw the start and end.
To draw a longer line, we can use a trick, Divide and Conquer, that has many applications in computer science: we divide our problem into two simpler problems. To draw a long line, we find the mid-point of the line, and then draw both halves of the line: from the start to the mid-point, and from the mid-point to the end. This algorithm is recursive, we solve the problem by solving simpler instances of the same problem. The note on Recursion gives more examples of this idea.
Bresenham's algorithm uses a different idea. We can describe a line as the intersection of two planes. One of these planes is the screen itself. The other cuts through the screen, along the line. It is simpler to describe the idea in terms of drawing a line on a piece of paper, lying horizontally. (Or you can imagine turning the monitor on its back so the screen lies horizontally, but please don't try this!) One of the planes is the paper itself, or the horizontal screen; the other lies at a slope, and cuts through the screen along the line.
An ant with an accurate altimeter, living on this slope, would find that moving away from the line in one direction it got higher, and in the other direction lower. Our ant could follow the line, using the altimeter, without the benefit of the second, horizontal, plane, by keeping at a constant height.This is the idea behind Bresenham's algorithm - except that we have to make do without an altimeter.
For the sake of our description, we'll consider a line going, roughly, from NorthWest to SouthEast. Suppose the ant knew that taking one step East increased its height by dx, and taking one step South decreased its height by dy. It could follow the line approximately, using only a compass, by repeatedly taking one step to the east followed by enough steps to the South to get back close to the original level. This is Bresenham's algorithm.
To go from x0,y0, in the NorthWest, to x1,y1, in the SouthEast, we choose a steeply sloping plane such that moving one step East increases our height by dx = y1-y0, and moving one step South decreases our height by dy = x1-x0. The point of choosing these particular numbers is that they are in the right proportions to make the slope match the line we want.
This form of the algorithm works best for lines with a gentle slope (less than 45 degrees). For steeper lines it's better to go South first, and then East to get back to the line, but the same idea can be transformed to work for lines in any direction.