Difference between revisions of "Bresenham's line algorithm"

From CodeCodex

Line 87: Line 87:
 
}
 
}
 
</pre>
 
</pre>
This code is implimented by Dharan P Deepak as part of an Academic assignment at Amrita University.
+
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 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 code can be compiled using javac <filename.java> and executed from command line by appletviewer <filename.java>
Line 94: Line 94:
 
[[Category:Java]]
 
[[Category:Java]]
 
[[Category:Graphics]]
 
[[Category:Graphics]]
 +
===OCaml===
 +
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]

Revision as of 02:20, 11 February 2007

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

Java

Here is a simple implementation of Bresenham's line algorithm

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

// <applet code="bresenham's line algorithm" 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

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]