Bresenham's line algorithm

From CodeCodex

Bresenham's line algorithm is an algorithm that determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics.

Implementations[edit]

C[edit]

 void rasterCircle(int x0, int y0, int radius)
 {
   int f = 1 - radius;
   int ddF_x = 0;
   int ddF_y = -2 * radius;
   int x = 0;
   int y = radius;
 
   setPixel(x0, y0 + radius);
   setPixel(x0, y0 - radius);
   setPixel(x0 + radius, y0);
   setPixel(x0 - radius, y0);
 
   while(x < y) 
   {
     if(f >= 0) 
     {
       y--;
       ddF_y += 2;
       f += ddF_y;
     }
     x++;
     ddF_x += 2;
     f += ddF_x + 1;    
     setPixel(x0 + x, y0 + y);
     setPixel(x0 - x, y0 + y);
     setPixel(x0 + x, y0 - y);
     setPixel(x0 - x, y0 - y);
     setPixel(x0 + y, y0 + x);
     setPixel(x0 - y, y0 + x);
     setPixel(x0 + y, y0 - x);
     setPixel(x0 - y, y0 - x);
   }
 }

Java[edit]

Here is a simple implementation of Bresenham's line algorithm

import java.applet.*;
import java.awt.*;
import java.awt.image.*;

// <applet code="bresenham'salgorithm" width="500" height="500"></applet>
public class bresenham'salgorithm extends Applet
{
	BufferedImage image =  new BufferedImage(100,150,BufferedImage.TYPE_INT_ARGB);
	WritableRaster raster  =  image.getRaster();
	
	int x0 = 60;
	int x1 = 50;
	int y0 = 10;
	int y1 = 20;

		

	int Dx = x0 - x1;
	int Dy = y0 - y1;
		
	int fraction,xstep,ystep;

	public void paint(Graphics g)
	{
		if(Dy < 0)
		{
			Dy = -Dy;
			ystep = -1;
		}
		else
		{
			ystep = 1;
		}
		if(Dx < 0)
		{
			Dx = - Dx;
			xstep = -1;
		}
		else
		{
			xstep = 1;
		}
		
		Dy <<= 1; 
		Dx <<= 1;
	
		int array[] = {250,0,0,250};
		raster.setPixel(x0,y0,array);
		if(Dx > Dy)
		{
			fraction = Dy - (Dx >> 1);
		} 
		while(x0 != x1)
		{
			if(fraction >= 0)
			{
				y0 += ystep;
				fraction -= Dx;
				x0 += xstep;
				fraction += Dy;
				raster.setPixel(x0,y0,array);
			}
			else
			{
				fraction = Dx-(Dy>>1);
				while(y0 != y1)
				{
					if(fraction >= 0)
					{
						x0 += xstep;
						fraction-=Dy;
					}
					y0 += ystep;
					fraction += Dx;
					raster.setPixel(x0,y0,array);
				}
			}
			g.drawImage(image,x1,y1,null);
		}
	}
}

This code is implemented by Dharan P Deepak as part of an Academic assignment at Amrita University. The code is developed in Mac OSX 10.4.8 and will work in all the platforms that are supported by Java. The code can be compiled using javac <filename.java> and executed from command line by appletviewer <filename.java> The Explanantion of the algorithm can be found in Wikipedia

OCaml[edit]

The following higher-order function implements Bresenham's line algorithm, assuming 0<=d<=q (i.e. for one octant):

 # let rec bresenham f accu d p q n = function
     | 0 -> accu
     | i ->
         let p = p + d in
         let p, n = if p>q then p-q, n+1 else p, n in
         bresenham f (f accu n) d p q n (i-1);;
 val bresenham :
   ('a -> int -> 'a) -> 'a -> int -> int -> int -> int -> int -> 'a = <fun>

For example, interpolating from 0 to 8 in 21 increments and prepending each result onto a list:

# bresenham (fun t h -> h::t) [] 3 0 7 0 21;;
- : int list =
[8; 8; 8; 7; 7; 6; 6; 5; 5; 5; 4; 4; 3; 3; 2; 2; 2; 1; 1; 0; 0]

Pseudo Basic[edit]

REM Bresenham Algorithm for one eighth of a circle in Pseudo-Basic
REM given: r, xmid, ymid
REM initialisations for the first octant
r2 = r*r : REM single multiplication
x = r
y = 0
error = r
SETPIXEL xmid + x, ymid + y

REM Pixel loop: always a step in fast direction, every now and then also in slow one
WHILE y <= x
   REM step in fast direction (positive y direction)
   dy = y*2+1 : REM in Assembler implementation *2 per Shift
   y = y+1
   error = error-dy
   IF error<0 THEN
      REM step in slow direction (here the negative x direction)
      dx = 1-x*2 : REM in Assembler implementation *2 per Shift
      x = x-1
      error = error-dx
      END IF
   SETPIXEL  xmid+x, ymid+y
   REM If this deals with a screen and not a mechanical plotter,
   REM you can cover simultaneously also the other octants:
   REM SETPIXEL xmid-x, ymid+y
   REM SETPIXEL xmid-x, ymid-y
   REM SETPIXEL xmid+x, ymid-y
   REM SETPIXEL xmid+y, ymid+x
   REM SETPIXEL xmid-y, ymid+x
   REM SETPIXEL xmid-y, ymid-x
   REM SETPIXEL xmid+y, ymid-x
   WEND

Ruby[edit]

# The line from the origin(0,0)
# (0,0)->(dx,dy)  0 <= dy <= dx (The angle range from 0 to 45 degrees)
def bresenham_0(dx, dy)
  dy = dy * 2
  y  = 1
  err = 0
  pos = []
  for x in 0..dx
    pos << [x, y/2]
    err += dy
    while err > dx
      y += 1
      err -= dx
    end
  end
  pos
end

# A straight line between two given points.
# (x0,y0) -> (x1,y1)
def bresenham(x0, y0, x1, y1)
  dx, dy = x1 - x0, y1 - y0
  sx, sy = dx<=>0, dy<=>0       # sign flag (-1,0 or 1)
  ax, ay = dx.abs, dy.abs
  if ax >= ay
    bresenham_0(ax, ay).map! {|x,y| [x0 + x * sx, y0 + y * sy]}
  else
    bresenham_0(ay, ax).map! {|y,x| [x0 + x * sx, y0 + y * sy]}
  end
end

p bresenham(0, 8, 8, 2)
#=> [[0, 8], [1, 7], [2, 7], [3, 6], [4, 5], [5, 4], [6, 4], [7, 3], [8, 2]]