Bitmap/Bresenham's line algorithm
Using the data storage type defined on this page for raster graphics images, draw a line given 2 points with the Bresenham's algorithm (definition on Wikipedia).
You are encouraged to solve this task according to the task description, using any language you may know.
Ada
<lang ada> procedure Line (Picture : in out Image; Start, Stop : Point; Color : Pixel) is
DX : constant Float := abs Float (Stop.X - Start.X); DY : constant Float := abs Float (Stop.Y - Start.Y); Err : Float; X : Positive := Start.X; Y : Positive := Start.Y; Step_X : Integer := 1; Step_Y : Integer := 1;
begin
if Start.X > Stop.X then Step_X := -1; end if; if Start.Y > Stop.Y then Step_Y := -1; end if; if DX > DY then Err := DX / 2.0; while X /= Stop.X loop Picture (X, Y) := Color; Err := Err - DY; if Err < 0.0 then Y := Y + Step_Y; Err := Err + DX; end if; X := X + Step_X; end loop; else Err := DY / 2.0; while Y /= Stop.Y loop Picture (X, Y) := Color; Err := Err - DX; if Err < 0.0 then X := X + Step_X; Err := Err + DY; end if; Y := Y + Step_Y; end loop; end if; Picture (X, Y) := Color; -- Ensure dots to be drawn
end Line; </lang> The test program's <lang ada>
X : Image (1..16, 1..16);
begin
Fill (X, White); Line (X, ( 1, 8), ( 8,16), Black); Line (X, ( 8,16), (16, 8), Black); Line (X, (16, 8), ( 8, 1), Black); Line (X, ( 8, 1), ( 1, 8), Black); Print (X);
</lang> sample output
H H H H H H HH H H H H H H H H H H H H H H H H H H H H H H H
ALGOL 68
MODE PIXEL = STRUCT(#SHORT# BITS red,green,blue); MODE IMAGE = [16,16]PIXEL, POINT = STRUCT(INT x,y); PIXEL black = (#SHORTEN# 16r00, #SHORTEN# 16r00, #SHORTEN# 16r00), red = (#SHORTEN# 16rff, #SHORTEN# 16r00, #SHORTEN# 16r00), green = (#SHORTEN# 16r00, #SHORTEN# 16rff, #SHORTEN# 16r00), blue = (#SHORTEN# 16r00, #SHORTEN# 16r00, #SHORTEN# 16rff), white = (#SHORTEN# 16rff, #SHORTEN# 16rff, #SHORTEN# 16rff); PROC fill = (REF IMAGE image, PIXEL color)VOID: BEGIN FOR x TO 1 UPB image DO FOR y TO 2 UPB image DO image[x,y] := color OD OD END; PROC line = (REF IMAGE picture, POINT start, stop, PIXEL color)VOID: BEGIN REAL dx = ABS (x OF stop - x OF start); REAL dy = ABS (y OF stop - y OF start); REAL err; INT x := x OF start; INT y := y OF start; INT step x := 1; INT step y := 1; IF x OF start > x OF stop THEN step x := -1 FI; IF y OF start > y OF stop THEN step y := -1 FI; IF dx > dy THEN err := dx / 2.0; WHILE x /= x OF stop DO picture[x,y] := color; err -:= dy; IF err < 0.0 THEN y +:= step y; err +:= dx FI; x +:= step x OD ELSE err := dy / 2.0; WHILE y /= y OF stop DO picture[x,y] := color; err := err - dx; IF err < 0.0 THEN x +:= step x; err +:= dy FI; y +:= step y OD FI; picture[x,y] := color # ensure dots to be drawn # END # line #; ### the test program's ### REF IMAGE x = LOC[1:16, 1:16]PIXEL; BEGIN fill (x, white); line (x, ( 1, 8), ( 8,16), black); line (x, ( 8,16), (16, 8), black); line (x, (16, 8), ( 8, 1), black); line (x, ( 8, 1), ( 1, 8), black); printf(($n(UPB x)(3(16r2d))l$, x)) END
Output:
ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffff000000ffffff000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff000000000000ffffffffffffffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffff ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffff 000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000 ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffff000000ffffff000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff
C
<lang c>#define plot(x, y) put_pixel_clip(img, x, y, r, g, b)
- define swap_uint(a, b) do{ unsigned int tmp; tmp = a; a = b; b = tmp; }while(0)
void draw_line(
image img, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1, color_component r, color_component g, color_component b )
{
unsigned short steep; steep = abs(y1 - y0) > abs(x1 - x0); if (steep) { swap_uint(x0, y0); swap_uint(x1, y1); } if (x0 > x1) { swap_uint(x0, x1); swap_uint(y0, y1); } { int deltax = x1 - x0; int deltay = abs(y1 - y0); int error = deltax / 2; int ystep; int y = y0; int x; if (y0 < y1) ystep = 1; else ystep = -1; for (x = x0; x <= x1; ++x) { if (steep) plot(y,x); else plot(x,y); error = error - deltay; if (error < 0) { y = y + ystep; error = error + deltax; } } }
}
- undef swap_uint
- undef plot</lang>
Forth
defer steep \ noop or swap defer ystep \ 1+ or 1- : line ( x0 y0 x1 y1 color bmp -- ) { color bmp } rot swap ( x0 x1 y0 y1 ) 2dup - abs >r 2over - abs r> < if ['] swap \ swap use of x and y else 2swap ['] noop then is steep ( y0 y1 x0 x1 ) 2dup > if swap 2swap swap \ ensure x1 > x0 else 2swap then ( x0 x1 y0 y1 ) 2dup > if ['] 1- else ['] 1+ then is ystep over - abs { y deltay } swap 2dup - dup { deltax } 2/ rot 1+ rot ( error x1+1 x0 ) do color i y steep bmp b! deltay - dup 0< if y ystep to y deltax + then loop drop ;
5 5 bitmap value test 0 test bfill 1 0 4 1 red test line 4 1 3 4 red test line 3 4 0 3 red test line 0 3 1 0 red test line test bshow cr ** * ** * * ** * ** ok
Fortran
<lang fortran>module RCImagePrimitive
use RCImageBasic
type point integer :: x, y end type point
private :: swapcoord
contains
subroutine swapcoord(p1, p2) integer, intent(inout) :: p1, p2 integer :: t
t = p2 p2 = p1 p1 = t end subroutine swapcoord
subroutine draw_line(img, from, to, color) type(rgbimage), intent(inout) :: img type(point), intent(in) :: from, to type(rgb), intent(in) :: color
type(point) :: rfrom, rto integer :: dx, dy, error, ystep, x, y logical :: steep
rfrom = from rto = to steep = (abs(rto%y - rfrom%y) > abs(rto%x - rfrom%x)) if ( steep ) then call swapcoord(rfrom%x, rfrom%y) call swapcoord(rto%x, rto%y) end if if ( rfrom%x > rto%x ) then call swapcoord(rfrom%x, rto%x) call swapcoord(rfrom%y, rto%y) end if
dx = rto%x - rfrom%x dy = abs(rto%y - rfrom%y) error = dx / 2 y = rfrom%y
if ( rfrom%y < rto%y ) then ystep = 1 else ystep = -1 end if
do x = rfrom%x, rto%x if ( steep ) then call put_pixel(img, y, x, color) else call put_pixel(img, x, y, color) end if error = error - dy if ( error < 0 ) then y = y + ystep error = error + dx end if end do
end subroutine draw_line
end module RCImagePrimitive</lang>
Usage example:
<lang fortran>program BasicImageTests
use RCImageBasic use RCImageIO use RCImagePrimitive
type(rgbimage) :: animage integer :: x, y
animage = alloc_img(200, 200) call fill_img(animage, rgb(255,255,255))
call draw_line(animage, point(0,0), point(199,199), rgb(0,0,0))
do y=0,219,20 call draw_line(animage, point(0,0), point(199, y), & rgb(0,0,0)) end do
open(unit=10, file='outputimage.ppm', status='new') call output_ppm(10, animage) close(10)
call free_img(animage)
end program BasicImageTests</lang>
MAXScript
fn plot img coord steep col = ( if steep then ( swap coord[1] coord[2] ) setPixels img coord col ) fn drawLine img start end col = ( local steep = (abs (end.y - start.y)) > (abs (end.x - start.x)) if steep then ( swap start.x start.y swap end.x end.y ) if start.x > end.x then ( swap start.x end.x swap start.y end.y ) local deltaX = end.x - start.x local deltaY = abs (end.y - start.y) local error = deltaX / 2.0 local yStep = -1 local y = start.y if start.y < end.y then ( yStep = 1 ) for x in start.x to end.x do ( plot img [x, y] steep col error -= deltaY if error < 0 then ( y += yStep error += deltaX ) ) img ) myBitmap = bitmap 512 512 color:(color 0 0 0) myBitmap = drawLine myBitmap [0, 511] [511, 0] #((color 255 255 255)) display myBitmap
OCaml
<lang ocaml>let draw_line ~img ~color ~p0:(x0,y0) ~p1:(x1,y1) =
let steep = abs(y1 - y0) > abs(x1 - x0) in
let plot = if steep then (fun x y -> put_pixel img color y x) else (fun x y -> put_pixel img color x y) in
let x0, y0, x1, y1 = if steep then y0, x0, y1, x1 else x0, y0, x1, y1 in let x0, x1, y0, y1 = if x0 > x1 then x1, x0, y1, y0 else x0, x1, y0, y1 in
let delta_x = x1 - x0 and delta_y = abs(y1 - y0) in let error = -delta_x / 2 and y_step = if y0 < y1 then 1 else -1 in let rec loop x y error = plot x y; if x <= x1 then let error = error + delta_y in let y, error = if error > 0 then (y + y_step), (error - delta_x) else y, error in loop (succ x) y error in loop x0 y0 error
- </lang>
RapidQ
Use this routine together with the code from Basic bitmap storage to create a full application.
<lang rapidq> SUB draw_line(x1, y1, x2, y2, colour)
x_dist = abs(x2-x1) y_dist = abs(y2-y1) IF y2-y1 < -x_dist OR x2-x1 <= -y_dist THEN SWAP x1, x2 ' Swap start and end points
SWAP y1, y2
END IF IF x1 < x2 THEN x_step = 1 ELSE x_step = -1 IF y1 < y2 THEN y_step = 1 ELSE y_step = -1 IF y_dist > x_dist THEN ' steep angle, step by y
error = y_dist/2 x = x1 FOR y = y1 TO y2 canvas.Pset(x, y, colour) error = error - x_dist IF error < 0 THEN x = x + x_step error = error + y_dist END IF NEXT y
ELSE ' not steep, step by x error = x_dist/2
y = y1 FOR x = x1 TO x2 canvas.Pset(x, y, colour) error = error - y_dist IF error < 0 THEN y = y + y_step error = error + x_dist END IF NEXT y
END IF
END SUB </lang>
Example usage:
<lang rapidq> SUB PaintCanvas
draw_line 200, 10, 100, 200, &H00ff00 draw_line 100, 200, 200, 400, &H00ff00 draw_line 200, 400, 300, 200, &H00ff00 draw_line 300, 200, 200, 10, &H00ff00
END SUB </lang>
Vedit macro language
// Daw a line using Bresenham's line algorithm. // #1=x1, #2=y1; #3=x2, #4=y2 :DRAW_LINE: Num_Push(31,35) #31 = abs(#3-#1) // x distance #32 = abs(#4-#2) // y distance if (#4-#2 < -#31 || #3-#1 <= -#32) { #99=#1; #1=#3; #3=#99 // swap start and end points #99=#2; #2=#4; #4=#99 } if (#1 < #3) { #34=1 } else { #34=-1 } // x step if (#2 < #4) { #35=1 } else { #35=-1 } // y step if (#32 > #31) { // steep angle, step by Y #33 = #32 / 2 // error distance while (#2 <= #4) { Call("DRAW_PIXEL") #33 -= #31 if (#33 < 0) { #1 += #34 // move right #33 += #32 } #2++ // move up } } else { // not steep, step by X #33 = #31 / 2 while (#1 <= #3) { Call("DRAW_PIXEL") #33 -= #32 if (#33 < 0) { #2 += #35 // move up #33 += #31 } #1++ // move right } } Num_Pop(31,35) return