View source for Bresenham's line algorithm

==Implementations==
===C===
<pre class="c">
 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);
   }
 }
</pre>
* Original Source: [http://en.wikipedia.org/wiki/Bresenham's_line_algorithm Wikipedia]

===Java===
Here is a simple implementation of Bresenham's line algorithm
<pre class="java">
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);
		}
	}
}
</pre>
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 [http://en.wikipedia.org/wiki/Bresenham's_line_algorithm Wikipedia]

===OCaml===
The following higher-order function implements Bresenham's line algorithm, assuming 0<=d<=q (i.e. for one octant):
<pre>
 # 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>
</pre>
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===
<pre>
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
</pre>
* Original Source: [http://en.wikipedia.org/wiki/Bresenham's_line_algorithm Wikipedia]

===Ruby===
<pre class="ruby">
# 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]]
</pre>

[[Category:BASIC]]
[[Category:C]]
[[Category:Java]]
[[Category:Objective Caml]]
[[Category:Ruby]]
[[Category:Graphics]]