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),
dy = ABS (y OF stop - y OF start);
REAL err;
POINT here := start,
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 -:= 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 #;
The test program:
IF test THEN
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