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 algol68>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
Instead of swaps in the initialisation use error calculation for both directions x and y simultaneously: <lang C>void line(int x0, int y0, int x1, int y1) {
int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1; int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1; int err = (dx>dy ? dx : -dy)/2, e2;
for(;;){ setPixel(x0,y0); if (x0==x1 && y0==y1) break; e2 = err; if (e2 >-dx) { err -= dy; x0 += sx; } if (e2 < dy) { err += dx; y0 += sy; } }
}</lang>
C++
<lang cpp> void Line( const float x1, const float y1, const float x2, const float y2, const Color& color ) {
// Bresenham's line algorithm
const bool steep = (fabs(y2 - y1) > fabs(x2 - x1)); if(steep) { std::swap(x1, y1); std::swap(x2, y2); }
if(x1 > x2) { std::swap(x1, x2); std::swap(y1, y2); }
const float dx = x2 - x1; const float dy = fabs(y2 - y1);
float error = dx / 2.0f; const int ystep = (y1 < y2) ? 1 : -1; int y = (int)y1;
const int maxX = (int)x2;
for(int x=(int)x1; x<maxX; x++) { if(steep)
{ SetPixel(y,x, color); }
else
{ SetPixel(x,y, color); } error -= dy;
if(error < 0) { y += ystep; error += dx; } } } </lang>
Clojure
<lang clojure> (defn draw-line
"Draw a line from x1,y1 to x2,y2 using Bresenham's, to a java BufferedImage in the colour of pixel." [buffer x1 y1 x2 y2 pixel] (let [dist-x (abs (- x1 x2))
dist-y (abs (- y1 y2)) steep (> dist-y dist-x)]
(let [[x1 y1 x2 y2] (if steep [y1 x1 y2 x2] [x1 y1 x2 y2])] (let [[x1 y1 x2 y2] (if (> x1 x2) [x2 y2 x1 y1] [x1 y1 x2 y2])]
(let [delta-x (- x2 x1) delta-y (abs (- y1 y2)) y-step (if (< y1 y2) 1 -1)]
(let [plot (if steep #(.setRGB buffer (int %1) (int %2) pixel) #(.setRGB buffer (int %2) (int %1) pixel))]
(loop [x x1 y y1 error (floor delta-x 2) ] (plot x y) (if (< x x2) ; Rather then rebind error, test that it is less than delta-y rather than zero (if (< error delta-y) (recur (inc x) (+ y y-step) (+ error (- delta-x delta-y))) (recur (inc x) y (- error delta-y))))))))))) </lang>
Common Lisp
<lang lisp>(defun draw-line (buffer x1 y1 x2 y2 pixel)
(declare (type rgb-pixel-buffer buffer)) (declare (type integer x1 y1 x2 y2)) (declare (type rgb-pixel pixel)) (let* ((dist-x (abs (- x1 x2)))
(dist-y (abs (- y1 y2))) (steep (> dist-y dist-x)))
(when steep (psetf x1 y1 y1 x1
x2 y2 y2 x2))
(when (> x1 x2) (psetf x1 x2 x2 x1
y1 y2 y2 y1))
(let* ((delta-x (- x2 x1))
(delta-y (abs (- y1 y2))) (error (floor delta-x 2)) (y-step (if (< y1 y2) 1 -1)) (y y1))
(loop
:for x :upfrom x1 :to x2 :do (progn (if steep (setf (rgb-pixel buffer x y) pixel) (setf (rgb-pixel buffer y x) pixel)) (setf error (- error delta-y)) (when (< error 0) (incf y y-step) (incf error delta-x)))))
buffer))</lang>
D
This example uses Bitmap structure template defined in Basic bitmap storage task.
This version uses direct pointers to the data to speed things up.
<lang D>// swap function template void swap(T)(ref T a, ref T b) { T t = a; a = b; b = t; } // absolute value, this could be taken from std.math or // tango.math.Math, but is placed here for convenience T labs(T)(T a) { return a < 0 ? -a : a; }
void drawLine(T)(Bitmap!(T) dest, int x0, int y0, int x1, int y1, T color) {
auto deltaY = labs(y1 - y0); auto deltaX = labs(x1 - x0); auto skew = deltaX > deltaY ? 1 : 0;
if (! skew ) { swap (deltaX, deltaY); swap (x0, y0); swap (x1, y1); }
auto d = (deltaY << 1) - deltaX; deltaX = (deltaY - deltaX) << 1; deltaY <<= 1;
if (x1 < x0) { swap (x0, x1); swap (y0, y1); }
int step = (x0 < x1 && y0 < y1) ? 1 : -1; if (skew) { T *ptr = &dest.data[y0*dest.width + x0]; for (; x0 < x1; x0++, ptr++) { *ptr = color; d += (d < 0) ? deltaY : deltaX; if (d >= 0) ptr += step*dest.width; } } else { T *ptr = &dest.data[x0*dest.width + y0]; for (; x0 < x1; x0++, ptr+=dest.width) { *ptr = color; d += (d < 0) ? deltaY : deltaX; if (d >= 0) ptr += step; }
}
}</lang>
Sample usage: <lang D>Rgb black; Rgb yellow = {[255, 255, 0]}; auto foobar = RgbBitmap(200, 100); drawLine(foobar, 20, 20, 180, 80, yellow); drawLine(foobar, 180, 20, 20, 80, yellow);</lang>
E
<lang e>def swap(&left, &right) { # From Generic swap
def t := left left := right right := t
}
def drawLine(image, var x0, var y0, var x1, var y1, color) {
def steep := (y1 - y0).abs() > (x1 - x0).abs() if (steep) { swap(&x0, &y0) swap(&x1, &y1) } if (x0 > x1) { swap(&x0, &x1) swap(&y0, &y1) } def deltax := x1 - x0 def deltay := (y1 - y0).abs() def ystep := if (y0 < y1) { 1 } else { -1 } var error := deltax // 2 var y := y0 for x in x0..x1 { if (steep) { image[y, x] := color } else { image[x, y] := color } error -= deltay if (error < 0) { y += ystep error += deltax } }
}</lang>
<lang e>def i := makeImage(5, 20) drawLine(i, 1, 1, 3, 18, makeColor.fromFloat(0,1,1)) i.writePPM(<import:java.io.makeFileOutputStream>(<file:~/Desktop/Bresenham.ppm>))</lang>
Erlang
<lang erlang> build_path({Sx, Sy}, {Tx, Ty}) -> if Tx < Sx -> StepX = -1; true -> StepX = 1 end, if Ty < Sy -> StepY = -1; true -> StepY = 1 end,
Dx = abs((Tx-Sx)*2), Dy = abs((Ty-Sy)*2),
if Dy > Dx -> Path = through_y({Sx, Sy}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, Dx*2-Dy, []); true -> Path = through_x({Sx, Sy}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, Dy*2-Dx, []) end,
lists:reverse(Path).
through_x({Tx, _}, {Tx, _}, _, _, _, P) -> P; through_x({Sx, Sy}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, F0, P) when F0 >= 0 -> Ny = Sy + StepY, F1 = F0 - Dx, Nx = Sx + StepX,
F2 = F1 + Dy,
through_x({Nx, Ny}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, F2, [{Nx, Ny}|P]); through_x({Sx, Sy}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, F0, P) when F0 < 0 -> Ny = Sy, Nx = Sx + StepX,
F2 = F0 + Dy,
through_x({Nx, Ny}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, F2, [{Nx, Ny}|P]).
through_y({_, Ty}, {_, Ty}, _, _, _, P) -> P; through_y({Sx, Sy}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, F0, P) when F0 >= 0 -> Nx = Sx + StepX, F1 = F0 - Dy, Ny = Sy + StepY,
F2 = F1 + Dx,
through_y({Nx, Ny}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, F2, [{Nx, Ny}|P]); through_y({Sx, Sy}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, F0, P) when F0 < 0 -> Nx = Sx, Ny = Sy + StepY,
F2 = F0 + Dx,
through_y({Nx, Ny}, {Tx, Ty}, {StepX, StepY}, {Dx, Dy}, F2, [{Nx, Ny}|P]). </lang> OR <lang erlang> line({X0, Y0}, {X1, Y1}) -> SX = step(X0, X1), SY = step(Y0, Y1), DX = abs(X1 - X0), DY = abs(Y1 - Y0), Err = DX - DY, line({X0, Y0}, {X1, Y1}, {SX, SY}, {DX, DY}, Err, []).
line({X1, Y1}, {X1, Y1}, _, _, _, Acc) -> lists:reverse([{X1, Y1} | Acc]); line({X, Y}, {X1, Y1}, {SX, SY}, {DX, DY}, Err, Acc) -> DE = 2 * Err, {X0, Err0} = next_x(X, SX, DY, Err, DE), {Y0, Err1} = next_y(Y, SY, DX, Err0, DE), line({X0, Y0}, {X1, Y1}, {SX, SY}, {DX, DY}, Err1, [{X, Y} | Acc]).
step(P0, P1) when P0 < P1 -> 1; step(_, _) -> -1.
next_x(X, SX, DY, E, DE) when DE > -DY -> {X + SX, E - DY}; next_x(X, _SX, _DY, E, _DE) -> {X, E}.
next_y(Y, SY, DX, E, DE) when DE < DX -> {Y + SY, E + DX}; next_y(Y, _SY, _DX, E, _DE) -> {Y, E}. </lang>
F#
<lang fsharp>let inline bresenham fill (x0, y0) (x1, y1) =
let steep = abs(y1 - y0) > abs(x1 - x0) let x0, y0, x1, y1 = if steep then y0, x0, y1, x1 else x0, y0, x1, y1 let x0, y0, x1, y1 = if x0 > x1 then x1, y1, x0, y0 else x0, y0, x1, y1 let dx, dy = x1 - x0, abs(y1 - y0) let s = if y0 < y1 then 1 else -1 let rec loop e x y = if x <= x1 then if steep then fill y x else fill x y if e < dy then loop (e-dy+dx) (x+1) (y+s) else loop (e-dy) (x+1) y loop (dx/2) x0 y0</lang>
The following program tests the above bresenham function by drawing 100 lines into an image and visualizing the result using
:
<lang fsharp>open System.Windows open System.Windows.Media.Imaging
[<System.STAThread>] do
let rand = System.Random() let n = 256 let pixel = Array.create (n*n) 0uy let rand = System.Random().Next for _ in 1..100 do bresenham (fun x y -> pixel.[x+y*n] <- 255uy) (rand n, rand n) (rand n, rand n) let image = Controls.Image(Stretch=Media.Stretch.Uniform) let format = Media.PixelFormats.Gray8 image.Source <- BitmapSource.Create(n, n, 1.0, 1.0, format, null, pixel, n) Window(Content=image, Title="Bresenham's line algorithm") |> (Application()).Run |> ignore</lang>
Factor
A very ugly imperative implementation similar to the wikipedia pseudocode.. <lang factor>USING: accessors arrays kernel locals math math.functions math.ranges math.vectors rosettacode.raster.display rosettacode.raster.storage sequences ui.gadgets ; IN: rosettacode.raster.line
- line-points ( pt1 pt2 -- points )
pt1 first2 :> y0! :> x0! pt2 first2 :> y1! :> x1! y1 y0 - abs x1 x0 - abs > :> steep steep [ y0 x0 y0! x0! y1 x1 y1! x1! ] when x0 x1 > [ x0 x1 x0! x1! y0 y1 y0! y1! ] when x1 x0 - :> deltax y1 y0 - abs :> deltay 0 :> current-error! deltay deltax / abs :> deltaerr 0 :> ystep! y0 :> y! y0 y1 < [ 1 ystep! ] [ -1 ystep! ] if x0 x1 1 <range> [ y steep [ swap ] when 2array current-error deltaerr + current-error! current-error 0.5 >= [ ystep y + y! current-error 1 - current-error! ] when ] { } map-as ;
! Needs rosettacode.raster.storage for the set-pixel function and to create the image
- draw-line ( {R,G,B} pt1 pt2 image -- )
[ line-points ] dip [ set-pixel ] curry with each ;</lang>
Forth
<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</lang>
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>
Go
<lang go>// often more convenient to supply rgb func (b *bitmap) lineRgb(x0, y0, x1, y1 int, c rgb) {
var p pixel p.setRgb(c) b.line(x0, y0, x1, y1, p)
}
// implemented straight from WP pseudocode func (b *bitmap) line(x0, y0, x1, y1 int, p pixel) {
dx := x1 - x0 if dx < 0 { dx = -dx } dy := y1 - y0 if dy < 0 { dy = -dy } var sx, sy int if x0 < x1 { sx = 1 } else { sx = -1 } if y0 < y1 { sy = 1 } else { sy = -1 } err := dx - dy
for { b.px[x0+y0*b.cols] = p if x0 == x1 && y0 == y1 { break } e2 := 2 * err if e2 > -dy { err -= dy x0 += sx } if e2 < dx { err += dx y0 += sy } }
}</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>
J
Solution:
Using definitions from Basic bitmap storage. <lang j>thru=: <./ + -~ i.@+ _1 ^ > NB. integers from x through y
NB.*getBresenhamLine v Returns points for a line given start and end points NB. y is: y0 x0 ,: y1 x1 getBresenhamLine=: monad define
steep=. ([: </ |@-~/) y points=. |."1^:steep y slope=. %~/ -~/ points ypts=. thru/ {."1 points xpts=. ({: + 0.5 <.@:+ slope * ypts - {.) {.points |."1^:steep ypts,.xpts
)
NB.*drawLines v Draws lines (x) on image (y) NB. x is: 2-item list (start and end points) ; (color) drawLines=: (1&{:: ;~ [: ; [: <@getBresenhamLine"2 (0&{::))@[ setPixels ]</lang>
Example Usage: <lang j> myimg=: 0 255 0 makeRGB 20 32 NB. 32 by 20 green image
myimg=: ((1 1 ,: 5 11) ; 255 0 0 ) drawLines myimg NB. draw red line from xy point 1 1 to 11 5
NB. Works for lists of 2 by 2 arrays each defining a line's start and end point.
Diamond=: _2]\ _2]\ 9 5 5 15 , 5 15 9 25 , 9 25 13 15 , 13 15 9 5 Square =: _2]\ _2]\ 5 5 5 25 , 5 25 13 25 , 13 25 13 5 , 13 5 5 5 viewRGB myimg=: (Diamond;255 0 0) drawLines myimg NB. draw 4 red lines to form a diamond viewRGB myimg=: (Square;0 0 255) drawLines myimg NB. draw 4 blue lines to form a square viewRGB (Diamond;255 0 0) drawLines (Square;0 0 255) drawLines myimg</lang>
JavaScript
Instead of swaps in the initialisation use error calculation for both directions x and y simultaneously: <lang javascript>function bline(x0, y0, x1, y1) {
var dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1; var dy = Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1; var err = (dx>dy ? dx : -dy)/2;
while (true) { setPixel(x0,y0); if (x0 === x1 && y0 === y1) break; var e2 = err; if (e2 > -dx) { err -= dy; x0 += sx; } if (e2 < dy) { err += dx; y0 += sy; } }
}</lang>
Maple
<lang maple>SegmentBresenham := proc (img, x0, y0, x1, y1)
local deltax, deltay, x, y, ystep, steep, err, img2, x02, y02, x12, y12; x02, x12, y02, y12 := y0, y1, x0, x1; steep := abs(x12 - x02) < abs(y12 - y02); img2 := copy(img); if steep then x02, y02 := y02, x02; x12, y12 := y12, x12; end if; if x12 < x02 then x02, x12 := x12, x02; y02, y12 := y12, y02; end if; deltax := x12 - x02; deltay := abs(y12 - y02); err := deltax / 2; y := y02; if y02 < y12 then ystep := 1 else ystep := -1 end if; for x from x02 to x12 do if steep then img2[y, x] := 0 else img2[x, y] := 0 end if; err := err - deltay; if err < 0 then y := y + ystep; err := err + deltax end if; end do; return img2;
end proc:</lang>
MAXScript
<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</lang>
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.
PL/I
<lang PL/I> /* Draw a line fom (x0, y0) to (x1, y1). 13 May 2010 */ /* Based on Rosetta code proforma. */ draw_line: procedure (xi, yi, xf, yf );
declare (xi, yi, xf, yf) fixed binary (31) nonassignable; declare (x0, y0, x1, y1) fixed binary (31); declare (deltax, deltay, x, y, ystep) fixed binary; declare (error initial (0), delta_error) float; declare steep bit (1);
x0 = xi; y = YI; y0 = yi; x1 = xf; y1 = yf; steep = abs(y1 - y0) > abs (x1 - x0); if steep then do; call swap (x0, y0); call swap (x1, y1); end; if x0 > x1 then do; call swap (x0, x1); call swap (y0, y1); end; deltax = x1 - x0; deltay = abs(y1 - y0); delta_error = deltay/deltax; if y0 < y1 then ystep = 1; else ystep = -1; do x = x0 to x1; if steep then image(y, x) = color; else image(x, y) = color; if steep then put skip list (y, x); else put skip list (x, y); error = error + delta_error; if error >= 0.5 then do; y = y + ystep; error = error - 1; end; end;
swap: procedure (a, b);
declare (a, b) fixed binary (31); declare t fixed binary (31); t = a; a = b; b = t;
end swap;
end draw_line; </lang>
Output from the statement:-
call draw_line(-1, -3, 6, 10);
for a -10:10 x -10:10 grid: <lang> ..........|.......... ..........|.......... ..........|.......... ..........|.......... ..........|.......... ..........|.......... ..........|.........* ..........|.......**. ..........|.....**... ..........|...**.....
+-**-------
..........**......... ........**|.......... .......*..|.......... ..........|.......... ..........|.......... ..........|.......... ..........|.......... ..........|.......... ..........|.......... ..........|.......... </lang>
PicoLisp
<lang PicoLisp>(de brez (Img X Y DX DY)
(let SX (cond ((=0 DX) 0) ((gt0 DX) 1) (T (setq DX (- DX)) -1) ) (let SY (cond ((=0 DY) 0) ((gt0 DY) 1) (T (setq DY (- DY)) -1) ) (if (>= DX DY) (let E (- (* 2 DY) DX) (do DX (set (nth Img Y X) 1) (when (ge0 E) (inc 'Y SY) (dec 'E (* 2 DX)) ) (inc 'X SX) (inc 'E (* 2 DY)) ) ) (let E (- (* 2 DX) DY) (do DY (set (nth Img Y X) 1) (when (ge0 E) (inc 'X SX) (dec 'E (* 2 DY)) ) (inc 'Y SY) (inc 'E (* 2 DX)) ) ) ) ) ) )
(let Img (make (do 90 (link (need 120 0)))) # Create image 120 x 90
(brez Img 10 10 100 30) # Draw five lines (brez Img 10 10 100 50) (brez Img 10 10 100 70) (brez Img 10 10 60 70) (brez Img 10 10 20 70) (out "img.pbm" # Write to bitmap file (prinl "P1") (prinl 120 " " 90) (mapc prinl Img) ) )</lang>
PureBasic
<lang PureBasic>Procedure BresenhamLine(x0 ,y0 ,x1 ,y1)
If Abs(y1 - y0) > Abs(x1 - x0); steep =#True Swap x0, y0 Swap x1, y1 EndIf If x0 > x1 Swap x0, x1 Swap y0, y1 EndIf deltax = x1 - x0 deltay = Abs(y1 - y0) error = deltax / 2 y = y0 If y0 < y1 ystep = 1 Else ystep = -1 EndIf For x = x0 To x1 If steep Plot(y,x) Else Plot(x,y) EndIf error - deltay If error < 0 y + ystep error + deltax EndIf Next
EndProcedure
- Window1 = 0
- Image1 = 0
- ImgGadget = 0
- width = 300
- height = 300
Define.i Event Define.f Angle
If OpenWindow(#Window1, 0, 0, #width, #height, "Bresenham's Line PureBasic Example", #PB_Window_SystemMenu|#PB_Window_ScreenCentered)
If CreateImage(#Image1, #width, #height) ImageGadget(#ImgGadget, 0, 0, #width, #height, ImageID(#Image1)) StartDrawing(ImageOutput(#Image1)) FillArea(0,0,-1,$FFFFFF) :FrontColor(0) While Angle < 2*#PI BresenhamLine(150,150,150+Cos(Angle)*120,150+Sin(Angle)*120) Angle + #PI/60 Wend StopDrawing() SetGadgetState(#ImgGadget, ImageID(#Image1)) Repeat Event = WaitWindowEvent() Until Event = #PB_Event_CloseWindow EndIf
EndIf</lang>
Python
Extending the example given here and using the algorithm from the ADA solution:
<lang python>def line(self, x0, y0, x1, y1):
"Bresenham's line algorithm" dx = abs(x1 - x0) dy = abs(y1 - y0) x, y = x0, y0 sx = -1 if x0 > x1 else 1 sy = -1 if y0 > y1 else 1 if dx > dy: err = dx / 2.0 while x != x1: self.set(x, y) err -= dy if err < 0: y += sy err += dx x += sx else: err = dy / 2.0 while y != y1: self.set(x, y) err -= dx if err < 0: x += sx err += dy y += sy self.set(x, y)
Bitmap.line = line
bitmap = Bitmap(17,17) for points in ((1,8,8,16),(8,16,16,8),(16,8,8,1),(8,1,1,8)):
bitmap.line(*points)
bitmap.chardisplay()
The origin, 0,0; is the lower left, with x increasing to the right, and Y increasing upwards.
The chardisplay above produces the following output : +-----------------+ | @ | | @ @ | | @ @ | | @ @ | | @ @ | | @ @ | | @ @ | | @ @ | | @ @| | @ @ | | @ @ | | @ @@ | | @ @ | | @ @ | | @ @ | | @ | | | +-----------------+ </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>
Ruby
<lang ruby>Pixel = Struct.new(:x, :y)
class Pixmap
def draw_line(p1, p2, colour) validate_pixel(p1.x, p2.y) validate_pixel(p2.x, p2.y)
x1, y1 = p1.x, p1.y x2, y2 = p2.x, p2.y steep = (y2 - y1).abs > (x2 - x1).abs if steep x1, y1 = y1, x1 x2, y2 = y2, x2 end if x1 > x2 x1, x2 = x2, x1 y1, y2 = y2, y1 end
deltax = x2 - x1 deltay = (y2 - y1).abs error = deltax / 2 ystep = y1 < y2 ? 1 : -1 y = y1 x1.upto(x2) do |x| pixel = steep ? [y,x] : [x,y] self[*pixel] = colour error -= deltay if error < 0 y += ystep error += deltax end end end
end
bitmap = Pixmap.new(500, 500) bitmap.fill(RGBColour::BLUE) 10.step(430, 60) do |a|
bitmap.draw_line(Pixel[10, 10], Pixel[490,a], RGBColour::YELLOW) bitmap.draw_line(Pixel[10, 10], Pixel[a,490], RGBColour::YELLOW)
end bitmap.draw_line(Pixel[10, 10], Pixel[490,490], RGBColour::YELLOW)</lang>
Scala
Uses the Scala Basic Bitmap Storage class. <lang scala>object BitmapOps {
def bresenham(bm:RgbBitmap, x0:Int, y0:Int, x1:Int, y1:Int, c:Color)={ val dx=math.abs(x1-x0) val sx=if (x0<x1) 1 else -1 val dy=math.abs(y1-y0) val sy=if (y0<y1) 1 else -1
def it=new Iterator[Tuple2[Int,Int]]{ var x=x0; var y=y0 var err=(if (dx>dy) dx else -dy)/2 def next={ val res=(x,y) val e2=err; if (e2 > -dx) {err-=dy; x+=sx} if (e2<dy) {err+=dx; y+=sy} res; } def hasNext=(x<=x1 && y<=y1) }
for((x,y) <- it) bm.setPixel(x, y, c) }
}</lang>
Tcl
ref Basic bitmap storage#Tcl <lang tcl>package require Tcl 8.5 package require Tk
proc drawLine {image colour point0 point1} {
lassign $point0 x0 y0 lassign $point1 x1 y1 set steep [expr {abs($y1 - $y0) > abs($x1 - $x0)}] if {$steep} { lassign [list $x0 $y0] y0 x0 lassign [list $x1 $y1] y1 x1 } if {$x0 > $x1} { lassign [list $x0 $x1] x1 x0 lassign [list $y0 $y1] y1 y0 } set deltax [expr {$x1 - $x0}] set deltay [expr {abs($y1 - $y0)}] set error [expr {$deltax / 2}] set ystep [expr {$y0 < $y1 ? 1 : -1}] for {set x $x0; set y $y0} {$x <= $x1} {incr x} { setPixel $image $colour [expr {$steep ? [list $y $x] : [list $x $y]}] incr error -$deltay if {$error < 0} { incr y $ystep incr error $deltax } }
}
- create the image and display it
set img [newImage 200 100] label .l -image $img pack .l
fill $img black drawLine $img yellow {20 20} {180 80} drawLine $img yellow {180 20} {20 80}</lang>
TI-89 BASIC
<lang ti89b>(lx0, ly0, lx1, ly1) Prgm
Local steep, x, y, dx, dy, ystep, error, tmp abs(ly1 - ly0) > abs(lx1 - lx0) → steep If steep Then lx0 → tmp ly0 → lx0 tmp → ly0 lx1 → tmp ly1 → lx1 tmp → ly1 EndIf If lx0 > lx1 Then lx0 → tmp lx1 → lx0 tmp → lx1 ly0 → tmp ly1 → ly0 tmp → ly1 EndIf lx1 - lx0 → dx abs(ly1 - ly0) → dy when(ly0 < ly1, 1, –1) → ystep intDiv(dx, 2) → error ly0 → y For x,lx0,lx1 If steep Then: PxlChg x, y :Else: PxlChg y, x :EndIf error - dy → error If error < 0 Then y + ystep → y error + dx → error EndIf EndFor
EndPrgm</lang>
Vedit macro language
<lang vedit>// 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</lang>