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.
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
<lang algol>PRAGMAT READ "Basic_bitmap_storage.a68" PRAGMAT;
line OF class image := (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; POINT here := start; POINT step := (1, 1); IF x OF start > x OF stop THEN x OF step := -1 FI; IF y OF start > y OF stop THEN y OF step := -1 FI; IF dx > dy THEN err := dx / 2; WHILE x OF here /= x OF stop DO picture[x OF here, y OF here] := color; err -:= dy; IF err < 0 THEN y OF here +:= y OF step; err +:= dx FI; x OF here +:= x OF step OD ELSE err := dy / 2; WHILE y OF here /= y OF stop DO picture[x OF here, y OF here] := color; err := err - dx; IF err < 0 THEN x OF here +:= x OF step; err +:= dy FI; y OF here +:= y OF step OD FI; picture[x OF here, y OF here] := color # ensure dots to be drawn #
END # line #;
IF test THEN
the test program's
REF IMAGE x = INIT LOC[1:16, 1:16]PIXEL; (fill OF class image)(x, white OF class image); (line OF class image)(x, ( 1, 8), ( 8,16), black OF class image); (line OF class image)(x, ( 8,16), (16, 8), black OF class image); (line OF class image)(x, (16, 8), ( 8, 1), black OF class image); (line OF class image)(x, ( 8, 1), ( 1, 8), black OF class image); (print OF class image)(x)
FI</lang> Output:
ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffff000000ffffff000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff000000000000ffffffffffffffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffff ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffff 000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000 ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffff000000ffffff000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff
C
To be added to imglib.h.
<lang c>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 );</lang>
The implementation code:
<lang c>#include "imglib.h"
- 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
implicit none
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
implicit none
type(rgbimage) :: animage integer :: x, y
call alloc_img(animage, 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>
Haskell
<lang haskell>module Bitmap.Line(line) where
import Bitmap import Control.Monad import Control.Monad.ST import qualified Data.STRef
var = Data.STRef.newSTRef get = Data.STRef.readSTRef mutate = Data.STRef.modifySTRef
line :: Color c => Image s c -> Pixel -> Pixel -> c -> ST s () line i (Pixel (xa, ya)) (Pixel (xb, yb)) c = do
yV <- var y1 errorV <- var $ deltax `div` 2 forM_ [x1 .. x2] (\x -> do y <- get yV setPix i (Pixel $ if steep then (y, x) else (x, y)) c mutate errorV $ subtract deltay error <- get errorV when (error < 0) (do mutate yV (+ ystep) mutate errorV (+ deltax))) where steep = abs (yb - ya) > abs (xb - xa) (xa', ya', xb', yb') = if steep then (ya, xa, yb, xb) else (xa, ya, xb, yb) (x1, y1, x2, y2) = if xa' > xb' then (xb', yb', xa', ya') else (xa', ya', xb', yb') deltax = x2 - x1 deltay = abs $ y2 - y1 ystep = if y1 < y2 then 1 else -1</lang>
Maple
<lang maple> SegmentBresenham := proc (img, x0, y0, x1, y1) local deltax, deltay, x, y, ystep, bool, e, img2, swap, x02, y02, x12, y12; x02 := y0; x12 := y1; y12 := x1; y02 := x0; bool := abs(x12-x02) < abs(y12-y02); img2 := copy(img); if bool then
swap := x02; x02 := y02; y02 := swap; swap := x12; x12 := y12; y12 := swap;
end if; if x12 < x02 then
swap := x02; x02 := x12; x12 := swap; swap := y02; y02 := y12; y12 := swap;
end if; deltax := x12-x02; deltay := abs(y12-y02); e := (1/2)*deltax; y := y02; if y02 < y12 then
ystep := 1 else ystep := -1; end if;
for x from x02 to x12 do
if bool then img2[y, x] := 0 else img2[x, y] := 0; end if; e := e-deltay; if e < 0 then y := y+ystep; e := e+deltax; end if;
end do; img2; end proc:</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>
Perl
<lang perl>#! /usr/bin/perl use strict; use Image::Imlib2;
sub my_draw_line {
my ( $img, $x0, $y0, $x1, $y1) = @_; my $steep = (abs($y1 - $y0) > abs($x1 - $x0)); if ( $steep ) {
( $y0, $x0 ) = ( $x0, $y0); ( $y1, $x1 ) = ( $x1, $y1 );
} if ( $x0 > $x1 ) {
( $x1, $x0 ) = ( $x0, $x1 ); ( $y1, $y0 ) = ( $y0, $y1 );
} my $deltax = $x1 - $x0; my $deltay = abs($y1 - $y0); my $error = $deltax / 2; my $ystep; my $y = $y0; my $x; $ystep = ( $y0 < $y1 ) ? 1 : -1; for( $x = $x0; $x <= $x1; $x += 1 ) {
if ( $steep ) { $img->draw_point($y, $x); } else { $img->draw_point($x, $y); } $error -= $deltay; if ( $error < 0 ) { $y += $ystep; $error += $deltax; }
}
}
- test
my $img = Image::Imlib2->new(160, 160); $img->set_color(255, 255, 255, 255); # white $img->fill_rectangle(0,0,160,160);
$img->set_color(0,0,0,255); # black my_draw_line($img, 10, 80, 80, 160); my_draw_line($img, 80, 160, 160, 80); my_draw_line($img, 160, 80, 80, 10); my_draw_line($img, 80, 10, 10, 80);
$img->save("test0.png");
- let's try the same using its internal algo
$img->set_color(255, 255, 255, 255); # white $img->fill_rectangle(0,0,160,160); $img->set_color(0,0,0,255); # black $img->draw_line(10, 80, 80, 160); $img->draw_line(80, 160, 160, 80); $img->draw_line(160, 80, 80, 10); $img->draw_line(80, 10, 10, 80);
$img->save("test1.png");
exit 0;</lang>
Images test0.png and test1.png look different since Imlib2 draw lines with antialiasing.
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