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
AutoHotkey
<lang AutoHotkey>Blue := Color(0,0,255) White := Color(255,255,255) Bitmap := Bitmap(100,100,Blue) ;create a 100*100 blue bitmap Line(Bitmap,White,5,10,60,80) ;draw a white line from (5,10) to (60,80) Bitmap.Write("Line.ppm") ;write the bitmap to file
Line(ByRef Bitmap,ByRef Color,PosX1,PosY1,PosX2,PosY2) {
DeltaX := Abs(PosX2 - PosX1), DeltaY := -Abs(PosY2 - PosY1) ;calculate deltas StepX := ((PosX1 < PosX2) ? 1 : -1), StepY := ((PosY1 < PosY2) ? 1 : -1) ;calculate steps ErrorValue := DeltaX + DeltaY ;calculate error value Loop ;loop over the pixel values { Bitmap[PosX1,PosX2] := Color If (PosX1 = PosX2 && PosY1 = PosY2) Break Temp1 := ErrorValue << 1, ((Temp1 > DeltaY) ? (ErrorValue += DeltaY, PosX1 += StepX) : ""), ((Temp1 < DeltaX) ? (ErrorValue += DeltaX, PosY1 += StepY) : "") ;move forward }
}</lang>
BBC BASIC
<lang bbcbasic> Width% = 200
Height% = 200 REM Set window size: VDU 23,22,Width%;Height%;8,16,16,128 REM Draw lines: PROCbresenham(50,100,100,190,0,0,0) PROCbresenham(100,190,150,100,0,0,0) PROCbresenham(150,100,100,10,0,0,0) PROCbresenham(100,10,50,100,0,0,0) END DEF PROCbresenham(x1%,y1%,x2%,y2%,r%,g%,b%) LOCAL dx%, dy%, sx%, sy%, e dx% = ABS(x2% - x1%) : sx% = SGN(x2% - x1%) dy% = ABS(y2% - y1%) : sy% = SGN(y2% - y1%) IF dx% < dy% e = dx% / 2 ELSE e = dy% / 2 REPEAT PROCsetpixel(x1%,y1%,r%,g%,b%) IF x1% = x2% IF y1% = y2% EXIT REPEAT IF dx% > dy% THEN x1% += sx% : e -= dy% : IF e < 0 e += dx% : y1% += sy% ELSE y1% += sy% : e -= dx% : IF e < 0 e += dy% : x1% += sx% ENDIF UNTIL FALSE ENDPROC DEF PROCsetpixel(x%,y%,r%,g%,b%) COLOUR 1,r%,g%,b% GCOL 1 LINE x%*2,y%*2,x%*2,y%*2 ENDPROC</lang>
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 code uses the Image defined in Bitmap Task.
<lang d>import std.algorithm, std.math, bitmap2;
void drawLine(Image img, double x1, double y1,
double x2, double y2, in Color color)
pure nothrow {
immutable steep = abs(y2 - y1) > abs(x2 - x1); if (steep) { swap(x1, y1); swap(x2, y2); }
if (x1 > x2) { swap(x1, x2); swap(y1, y2); }
immutable dx = x2 - x1; immutable float dy = abs(y2 - y1); immutable int ystep = (y1 < y2) ? 1 : -1; immutable maxX = cast(int)x2;
auto error = dx / 2.0; auto y = cast(int)y1;
foreach (immutable x; cast(int)x1 .. maxX) { if (steep) img[x][y] = color; else img[y][x] = color;
error -= dy; if (error < 0) { y += ystep; error += dx; } }
}
version (bitmap_bresenhams_main) {
void main() { auto img = new Image(25, 25); img.drawLine(5, 5, 15, 20, Color.white); img.drawLine(3, 20, 10, 12, Color.white); img.textualShow(); }
}</lang>
To run the demo code compile with -version=bitmap_bresenhams_main
.
- Output:
######################### ######################### ######################### ######################### ######################### #####.################### ######.################## ######.################## #######.################# ########.################ ########.################ #########.############### ##########.############## #########..############## ########.##.############# #######.####.############ #######.####.############ ######.######.########### #####.########.########## ####.#########.########## ######################### ######################### ######################### ######################### #########################
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>
Euphoria
<lang euphoria>include std/console.e include std/graphics.e include std/math.e
-- the new_image function and related code in the 25 or so -- lines below are from http://rosettacode.org/wiki/Basic_bitmap_storage#Euphoria -- as of friday, march 2, 2012
-- Some color constants: constant
black = #000000, white = #FFFFFF, red = #FF0000, green = #00FF00, blue = #0000FF
-- Create new image filled with some color function new_image(integer width, integer height, atom fill_color)
return repeat(repeat(fill_color,height),width)
end function
--grid used for drawing lines in this program sequence screenData = new_image(16,16,black)
--the line algorithm function bresLine(sequence screenData, integer x0, integer y0, integer x1, integer y1, integer color)
integer deltaX = abs(x1 - x0), deltaY = abs(y1 - y0) integer stepX, stepY, lineError, error2 if x0 < x1 then stepX = 1 else stepX = -1 end if
if y0 < y1 then stepY = 1 else stepY = -1 end if if deltaX > deltaY then lineError = deltaX else lineError = -deltaY end if lineError = round(lineError / 2, 1) while 1 do screenData[x0][y0] = color if (x0 = x1 and y0 = y1) then exit end if error2 = lineError if error2 > -deltaX then lineError -= deltaY x0 += stepX end if if error2 < deltaY then lineError += deltaX y0 += stepY end if end while return screenData -- return modified version of the screenData sequence
end function
--prevents console output wrapping to next line if it is too big for the screen wrap(0) --outer diamond screenData = bresLine(screenData,8,1,16,8,white) screenData = bresLine(screenData,16,8,8,16,white) screenData = bresLine(screenData,8,16,1,8,white) screenData = bresLine(screenData,1,8,8,1,white) --inner diamond screenData = bresLine(screenData,8,4,12,8,white) screenData = bresLine(screenData,12,8,8,12,white) screenData = bresLine(screenData,8,12,4,8,white) screenData = bresLine(screenData,4,8,8,4,white) -- center lines drawing from left to right, and the next from right to left. screenData = bresLine(screenData,7,7,9,7,white) screenData = bresLine(screenData,9,9,7,9,white) --center dot screenData = bresLine(screenData,8,8,8,8,white)
--print to the standard console output for i = 1 to 16 do
puts(1,"\n") for j = 1 to 16 do if screenData[j][i] = black then printf(1, "%s", ".") else printf(1, "%s", "#") end if end for
end for
puts(1,"\n\n") any_key()
--/* --output was edited to replace the color's hex digits for clearer output graphics. --to output all the hex digits, use printf(1,"%06x", screenData[j][i]) --to output 'shortened' hex digits, use : --printf(1, "%x", ( abs( ( (screenData[j][i] / #FFFFF) - 1 ) ) - 1 ) ) --and --printf(1,"%x", abs( ( (screenData[j][i] / #FFFFF) - 1 ) ) ) -- --,respectively in the last if check. --*/</lang> Output:
.......#........ ......#.#....... .....#...#...... ....#..#..##.... ...#..#.#...#... ..#..#...#...#.. .#..#.###.#...#. #..#...#...#...# .#..#.###.#...#. ..#..#...#...#.. ...#..#.#...#... ....#..#...#.... ....#.....#..... .....#...#...... ......#.#....... .......#........ Press Any Key to continue...
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>package raster
// Line draws line by Bresenham's algorithm. func (b *Bitmap) Line(x0, y0, x1, y1 int, p Pixel) {
// implemented straight from WP pseudocode 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.SetPx(x0, y0, p) if x0 == x1 && y0 == y1 { break } e2 := 2 * err if e2 > -dy { err -= dy x0 += sx } if e2 < dx { err += dx y0 += sy } }
}
func (b *Bitmap) LineRgb(x0, y0, x1, y1 int, c Rgb) {
b.Line(x0, y0, x1, y1, c.Pixel())
}</lang> A demonstration program: <lang go>package main
// Files required to build supporting package raster are found in: // * This task (immediately above) // * Bitmap // * Write a PPM file
import (
"raster" "fmt"
)
func main() {
b := raster.NewBitmap(400, 300) b.FillRgb(0xdfefff) blue := raster.Rgb(0x8fcfff) b.LineRgb(7, 12, 307, 122, blue) b.LineRgb(177, 12, 127, 222, blue) err := b.WritePpmFile("bresenham.ppm") if err != nil { fmt.Println(err) }
}</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>
Korn Shell
<lang>function line {
x0=$1; y0=$2 x1=$3; y1=$4
if (( x0 > x1 )) then ((dx = x0 - x1)); ((sx = -1)) else ((dx = x1 - x0)); ((sx = 1)) fi
if (( y0 > y1 )) then ((dy = y0 - y1)); ((sy = -1)) else ((dy = y1 - y0)); ((sy = 1)) fi
if (( dx > dy )) then ((err = dx)) else ((err = -dy)) fi ((err /= 2)); ((e2 = 0))
while /bin/true do echo $x0 $y0 (( x0 == x1 && y0 == y1 )) && return ((e2 = err)) (( e2 > -dx)) && { ((err -= dy )); (( x0 += sx )) } (( e2 < dy)) && { ((err += dx )); (( y0 += sy )) }
done
}</lang>
Output from the statement:-
line 0 0 3 4
(which could be piped to another program) <lang>0 0 1 1 1 2 2 3 3 4</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>
Mathematica
<lang Mathematica>Rasterize[ Style[Graphics[Line[{{0, 0}, {20, 10}}]], Antialiasing -> False]] </lang>
MATLAB
Note: Store this function in a file named "bresenhamLine.m" in the @Bitmap folder for the Bitmap class defined here.
<lang MATLAB> %screen = Bitmap object %startPoint = [x0,y0] %endPoint = [x1,y1] %color = [red,green,blue]
function bresenhamLine(screen,startPoint,endPoint,color)
if( any(color > 255) ) error 'RGB colors must be between 0 and 255'; end
%Check for vertical line, x0 == x1 if( startPoint(1) == endPoint(1) ) %Draw vertical line for i = (startPoint(2):endPoint(2)) setPixel(screen,[startPoint(1) i],color); end end
%Simplified Bresenham algorithm dx = abs(endPoint(1) - startPoint(1)); dy = abs(endPoint(2) - startPoint(2)); if(startPoint(1) < endPoint(1)) sx = 1; else sx = -1; end if(startPoint(2) < endPoint(2)) sy = 1; else sy = -1; end err = dx - dy; pixel = startPoint; while(true) screen.setPixel(pixel,color); %setPixel(x0,y0) if( pixel == endPoint ) break; end e2 = 2*err; if( e2 > -dy ) err = err - dy; pixel(1) = pixel(1) + sx; end if( e2 < dx ) err = err + dx; pixel(2) = pixel(2) + sy; end end assignin('caller',inputname(1),screen); %saves the changes to the object
end </lang>
Sample Usage: <lang MATLAB> >> img = Bitmap(800,600); >> img.bresenhamLine([400 550],[200 400],[255 255 255]); >> img.bresenhamLine([400 550],[600 400],[255 255 255]); >> img.bresenhamLine([200 400],[350 150],[255 255 255]); >> img.bresenhamLine([600 400],[450 150],[255 255 255]); >> img.bresenhamLine([350 150],[450 150],[255 255 255]); >> img.bresenhamLine([400 550],[400 150],[255 255 255]); >> disp(img) </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.
Perl 6
<lang perl6>sub line(Bitmap $bitmap, $x0 is copy, $x1 is copy, $y0 is copy, $y1 is copy) {
my $steep = abs($y1 - $y0) > abs($x1 - $x0); if $steep { ($x0, $y0) = ($y0, $x0); ($x1, $y1) = ($y1, $x1); } if $x0 > $x1 { ($x0, $x1) = ($x1, $x0); ($y0, $y1) = ($y1, $y0); } my $Δx = $x1 - $x0; my $Δy = abs($y1 - $y0); my $error = 0; my $Δerror = $Δy / $Δx; my $y-step = $y0 < $y1 ?? 1 !! -1; my $y = $y0; for $x0 .. $x1 -> $x { my $pix = Pixel.new(R => 100, G => 200, B => 0); if $steep { $bitmap.set-pixel($y, $x, $pix); } else { $bitmap.set-pixel($x, $y, $pix); } $error += $Δerror; if $error >= 0.5 { $y += $y-step; $error -= 1.0; } }
}</lang>
PL/I
<lang PL/I> /* Draw a line from (x0, y0) to (x1, y1). 13 May 2010 */ /* Based on Rosetta code proforma. */
/* Declarations for image and selected color, for 4-bit colors. */ declare image(40,40) bit (4), color bit (4) static initial ('1000'b);
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>
REXX
This REXX program is modeled after the PL/I version. <lang rexx>/*REXX program plots/draws a line using the Bresenham's line algorithm. */
EoE = 1000 /*EOE = End Of Earth, er, plot. */ image. = 'fa'x /*fill the array with middle-dots*/ plotC = 'fe'x /*character used for plotting pts*/
do j=-EoE to +EoE /*draw grid from lowest──>highest*/ image.j.0 = '─' /*draw the horizontal axis. */ image.0.j = '│' /* " " verical " */ end /*j*/
image.0.0='┼' /*"draw" the axis origin. */ parse arg xi yi xf yf . /*allow specifying line-end pts. */ if xi== | xi==',' then xi = -1 /*if not specified, use default. */ if yi== | yi==',' then yi = -3 /* " " " " " */ if xf== | xf==',' then xf = 6 /* " " " " " */ if yf== | yf==',' then yf = 10 /* " " " " " */ call draw_line xi, yi, xf, yf /*call subroutine and draw line. */ call findMaxXY
do y=maxY by -1 to minY; aRow= do x=minX to maxX aRow=aRow || image.x.y end /*x*/ say aRow end /*y*/
exit /*────────────────────────────────DRAW_LINE subroutine──────────────────*/ draw_line: procedure expose image. plotC; error=0 parse arg xi 1 x0, yi 1 y0 1 y, xf 1 x1, yf 1 y1 steep= abs(y1-y0) > abs(x1-x0) if steep then parse value x0 y0 x1 y1 with y0 x0 y1 x1 if x0>x1 then parse value x0 x1 y0 y1 with x1 x0 y1 y0
if y0<y1 then yInc = 1 else yInc = -1
deltaE=abs(y1-y0) / (x1-x0)
do x=x0 to x1 if steep then image.y.x=plotC else image.x.y=plotC error=error+deltaE if error>=.5 then do; y=y+yInc; error=error-1; end end
return /*────────────────────────────────FINDMAXXY subroutine──────────────────*/ findMaxXY: extra=3 /*don't just show cropped plot. */
do minX=-EoE to +EoE /*find min X in the plot field. */ do y=-EoE to +EoE; if .isP(image.minX.y) then leave minX; end /*y*/ end /*minX*/
do maxX=+EoE to -EoE by -1 /*find max X in the plot field. */ do y=-EoE to +EoE; if .isP(image.maxX.y) then leave maxX; end /*y*/ end /*maxX*/
do minY=-EoE to +EoE /*find min Y in the plot field. */ do x=-EoE to +EoE; if .isP(image.x.minY) then leave minY; end /*x*/ end /*minY*/
do maxY=+EoE to -EoE by -1 /*find max Y in the plot field. */ do x=-EoE to +EoE; if .isP(image.X.maxy) then leave maxY; end /*x*/ end /*maxY*/
minX=minX-extra*2; minY=minY-extra /*like showbiz, show a little more*/ maxX=maxX+extra*2; maxY=maxY+extra /* " " " " " " */ return /*go ye forth and show ye plot. */ .isP: return pos(arg(1),plotC)\==0</lang> output when using the default input
·········│·········· ·········│·········· ·········│·········· ·········│···■······ ·········│··■······· ·········│··■······· ·········│·■········ ·········│·■········ ·········│■········· ·········│■········· ·········■·········· ·········■·········· ········■│·········· ────────■┼────────── ·······■·│·········· ·······■·│·········· ······■··│·········· ·········│·········· ·········│·········· ·········│··········
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>
XPL0
Bresenham line draw is built-in. <lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations [SetVid($112); \set 640x480 graphics in 24-bit color Move(10, 20); \set start of line segment Line(600, 400, $123456);\draw line segment, red=$12, green=$34, blue=$56 if ChIn(1) then []; \wait for keystroke while viewing graphic screen SetVid(3); \restore normal text mode ]</lang>