Bitmap/Bresenham's line algorithm
From Rosetta Code
< Bitmap
You are encouraged to solve this task according to the task description, using any language you may know.
Using the data storage type defined on this page for raster graphics images, draw a line given 2 points with the Bresenham's algorithm.
Contents |
[edit] 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;
The test program's
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);
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
[edit] ALGOL 68
Translation of: Ada
Works with: ALGOL 68 version Standard - pragmat read is an extension Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
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
Output:
ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffff000000ffffff000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff000000000000ffffffffffffffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffff ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffff 000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000 ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffff000000ffffff000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff
[edit] C
To be added to imglib.h.
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 );
The implementation code:
#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 )
{
bool 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;
if (y0 < y1)
ystep = 1;
else
ystep = -1;
for (int x = x0; x <= x1; x++) {
if (steep)
plot(y, x);
else
plot(x, y);
error -= deltay;
if (error < 0) {
y += ystep;
error += deltax;
}
}
}
#undef swap_uint
#undef plot
[edit] 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)))))))))))
[edit] Common 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))
[edit] 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.
// 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;
}
}
}
Sample usage:
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);
[edit] E
Translation of: C
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
}
}
}
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>))
[edit] 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]).
[edit] F#
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
The following program tests the above bresenham function by drawing 100 lines into an image and visualizing the result using Library: Windows Presentation Foundation:
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
[edit] Factor
A very ugly imperative implementation similar to the wikipedia pseudocode..
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 ;
[edit] 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
[edit] Fortran
Works with: Fortran version 90 and later Translation of: C
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
Usage example:
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
[edit] 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
[edit] J
Solution:
Using definitions from Basic bitmap storage.
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 ]
Example Usage:
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
[edit] 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:
[edit] 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
[edit] 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
;;
[edit] Perl
Library: Imlib2
#! /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;
Images test0.png and test1.png look different since Imlib2 draw lines with antialiasing.
[edit] 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;
Output from the statement:-
call draw_line(-1, -3, 6, 10);
for a -10:10 x -10:10 grid:
..........|..........
..........|..........
..........|..........
..........|..........
..........|..........
..........|..........
..........|.........*
..........|.......**.
..........|.....**...
..........|...**.....
----------+-**-------
..........**.........
........**|..........
.......*..|..........
..........|..........
..........|..........
..........|..........
..........|..........
..........|..........
..........|..........
..........|..........
[edit] 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 NIL 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) ) )
[edit] 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
[edit] Python
Works with: Python version 3.1
Extending the example given here and using the algorithm from the ADA solution:
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 :
+-----------------+
| @ |
| @ @ |
| @ @ |
| @ @ |
| @ @ |
| @ @ |
| @ @ |
| @ @ |
| @ @|
| @ @ |
| @ @ |
| @ @@ |
| @ @ |
| @ @ |
| @ @ |
| @ |
| |
+-----------------+
'''
[edit] RapidQ
Use this routine together with the code from Basic bitmap storage to create a full application.
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
Example usage:
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
[edit] 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)
[edit] Tcl
Library: Tk ref Basic bitmap storage#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}
[edit] TI-89 BASIC
Translation of: E
(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
[edit] 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
Categories: Programming Tasks | Raster graphics operations | Graphics algorithms | Ada | ALGOL 68 | C | Clojure | Common Lisp | D | E | Erlang | F Sharp | Windows Presentation Foundation | Factor | Forth | Fortran | Haskell | J | Maple | MAXScript | OCaml | Perl | Imlib2 | PL/I | PicoLisp | PureBasic | Python | RapidQ | Ruby | Tcl | Tk | TI-89 BASIC | Vedit macro language
