CS U540 Sample Problems


      (Bresenham Line Algorithm)

Show the values of the decision function and the pixels selected by the Bresenham line algorithm for the line from (3, 2) to (11, 7).

Bresenham's Line Algorithm for |m| < 1

1.  Input the two endpoints and store the left endpoint in (x0, y0).
2.  Load (x0, y0) into the frame buffer; i.e. plot the first point.
3.  Calculate the constants deltax, deltay, 2deltay, and 2deltay - 2deltax, and 
     obtain the starting value for the decision function p0 = 2deltay - deltax.
4.  At each xk along the line, starting at k = 0, perform the following test:
     If pk < 0, the next point to plot is (xk + 1, yk) and pk+1 = pk + 2deltay.
    Otherwise the next point to plot is (xk + 1, yk + 1) and 
	   pk +1 = pk + 2deltay - 2deltax.
5.  Repeat step 4 deltax times.
For the region shown below, assume BoundaryValue = black, FillValue = gray and that SEED_FILL(4, 6) has been called.

kpk   xy
  32
0 4 
1 5 
2 6 
3 7 
4 8 
5 9 
6 10 
7 117


Last Updated: May 27, 2004 5:20 p.m. by
Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #WHV-340,
Boston, MA 02115
Internet: fell@ccs.neu.edu
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/CSU540/exams/BresenhamProblem.html