Bitmap/Bresenham's line algorithm: Difference between revisions
m →{{header|Fortran}}: fixed wrong bounds |
m Use wp: link. |
||
Line 1:
{{task|Raster graphics operations}}
Using the data storage type defined [[Basic_bitmap_storage|on this page]] for raster graphics images, draw a line given 2 points with the
=={{header|Ada}}==
|
Revision as of 19:23, 18 February 2009
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.
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
MODE PIXEL = STRUCT(#SHORT# BITS red,green,blue); MODE IMAGE = [16,16]PIXEL, POINT = STRUCT(INT x,y); PIXEL black = (#SHORTEN# 16r00, #SHORTEN# 16r00, #SHORTEN# 16r00), red = (#SHORTEN# 16rff, #SHORTEN# 16r00, #SHORTEN# 16r00), green = (#SHORTEN# 16r00, #SHORTEN# 16rff, #SHORTEN# 16r00), blue = (#SHORTEN# 16r00, #SHORTEN# 16r00, #SHORTEN# 16rff), white = (#SHORTEN# 16rff, #SHORTEN# 16rff, #SHORTEN# 16rff); PROC fill = (REF IMAGE image, PIXEL color)VOID: BEGIN FOR x TO 1 UPB image DO FOR y TO 2 UPB image DO image[x,y] := color OD OD END; PROC line = (REF IMAGE picture, POINT start, stop, PIXEL color)VOID: BEGIN REAL dx = ABS (x OF stop - x OF start); REAL dy = ABS (y OF stop - y OF start); REAL err; INT x := x OF start; INT y := y OF start; INT step x := 1; INT step y := 1; IF x OF start > x OF stop THEN step x := -1 FI; IF y OF start > y OF stop THEN step y := -1 FI; IF dx > dy THEN err := dx / 2.0; WHILE x /= x OF stop DO picture[x,y] := color; err -:= dy; IF err < 0.0 THEN y +:= step y; err +:= dx FI; x +:= step x OD ELSE err := dy / 2.0; WHILE y /= y OF stop DO picture[x,y] := color; err := err - dx; IF err < 0.0 THEN x +:= step x; err +:= dy FI; y +:= step y OD FI; picture[x,y] := color # ensure dots to be drawn # END # line #; ### the test program's ### REF IMAGE x = LOC[1:16, 1:16]PIXEL; 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); printf(($n(UPB x)(3(16r2d))l$, x)) END
Output:
ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffff000000ffffff000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff000000000000ffffffffffffffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffff ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffff 000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000 ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffff000000ffffff000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff
C
<lang c>#define plot(x, y) put_pixel_clip(img, x, y, r, g, b)
- define swap_uint(a, b) do{ unsigned int tmp; tmp = a; a = b; b = tmp; }while(0)
void draw_line(
image img, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1, color_component r, color_component g, color_component b )
{
unsigned short steep; steep = abs(y1 - y0) > abs(x1 - x0); if (steep) { swap_uint(x0, y0); swap_uint(x1, y1); } if (x0 > x1) { swap_uint(x0, x1); swap_uint(y0, y1); } { int deltax = x1 - x0; int deltay = abs(y1 - y0); int error = deltax / 2; int ystep; int y = y0; int x; if (y0 < y1) ystep = 1; else ystep = -1; for (x = x0; x <= x1; ++x) { if (steep) plot(y,x); else plot(x,y); error = error - deltay; if (error < 0) { y = y + ystep; error = error + deltax; } } }
}
- undef swap_uint
- undef plot</lang>
Forth
defer steep \ noop or swap defer ystep \ 1+ or 1- : line ( x0 y0 x1 y1 color bmp -- ) { color bmp } rot swap ( x0 x1 y0 y1 ) 2dup - abs >r 2over - abs r> < if ['] swap \ swap use of x and y else 2swap ['] noop then is steep ( y0 y1 x0 x1 ) 2dup > if swap 2swap swap \ ensure x1 > x0 else 2swap then ( x0 x1 y0 y1 ) 2dup > if ['] 1- else ['] 1+ then is ystep over - abs { y deltay } swap 2dup - dup { deltax } 2/ rot 1+ rot ( error x1+1 x0 ) do color i y steep bmp b! deltay - dup 0< if y ystep to y deltax + then loop drop ;
5 5 bitmap value test 0 test bfill 1 0 4 1 red test line 4 1 3 4 red test line 3 4 0 3 red test line 0 3 1 0 red test line test bshow cr ** * ** * * ** * ** ok
Fortran
<lang fortran>module RCImagePrimitive
use RCImageBasic
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
type(rgbimage) :: animage integer :: x, y
animage = alloc_img(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>
MAXScript
fn plot img coord steep col = ( if steep then ( swap coord[1] coord[2] ) setPixels img coord col ) fn drawLine img start end col = ( local steep = (abs (end.y - start.y)) > (abs (end.x - start.x)) if steep then ( swap start.x start.y swap end.x end.y ) if start.x > end.x then ( swap start.x end.x swap start.y end.y ) local deltaX = end.x - start.x local deltaY = abs (end.y - start.y) local error = deltaX / 2.0 local yStep = -1 local y = start.y if start.y < end.y then ( yStep = 1 ) for x in start.x to end.x do ( plot img [x, y] steep col error -= deltaY if error < 0 then ( y += yStep error += deltaX ) ) img ) myBitmap = bitmap 512 512 color:(color 0 0 0) myBitmap = drawLine myBitmap [0, 511] [511, 0] #((color 255 255 255)) display myBitmap
OCaml
<lang ocaml>let draw_line ~img ~color ~p0:(x0,y0) ~p1:(x1,y1) =
let steep = abs(y1 - y0) > abs(x1 - x0) in
let plot = if steep then (fun x y -> put_pixel img color y x) else (fun x y -> put_pixel img color x y) in
let x0, y0, x1, y1 = if steep then y0, x0, y1, x1 else x0, y0, x1, y1 in let x0, x1, y0, y1 = if x0 > x1 then x1, x0, y1, y0 else x0, x1, y0, y1 in
let delta_x = x1 - x0 and delta_y = abs(y1 - y0) in let error = -delta_x / 2 and y_step = if y0 < y1 then 1 else -1 in let rec loop x y error = plot x y; if x <= x1 then let error = error + delta_y in let y, error = if error > 0 then (y + y_step), (error - delta_x) else y, error in loop (succ x) y error in loop x0 y0 error
- </lang>
RapidQ
Use this routine together with the code from Basic bitmap storage to create a full application.
<lang rapidq> SUB draw_line(x1, y1, x2, y2, colour)
x_dist = abs(x2-x1) y_dist = abs(y2-y1) IF y2-y1 < -x_dist OR x2-x1 <= -y_dist THEN SWAP x1, x2 ' Swap start and end points
SWAP y1, y2
END IF IF x1 < x2 THEN x_step = 1 ELSE x_step = -1 IF y1 < y2 THEN y_step = 1 ELSE y_step = -1 IF y_dist > x_dist THEN ' steep angle, step by y
error = y_dist/2 x = x1 FOR y = y1 TO y2 canvas.Pset(x, y, colour) error = error - x_dist IF error < 0 THEN x = x + x_step error = error + y_dist END IF NEXT y
ELSE ' not steep, step by x error = x_dist/2
y = y1 FOR x = x1 TO x2 canvas.Pset(x, y, colour) error = error - y_dist IF error < 0 THEN y = y + y_step error = error + x_dist END IF NEXT y
END IF
END SUB </lang>
Example usage:
<lang rapidq> SUB PaintCanvas
draw_line 200, 10, 100, 200, &H00ff00 draw_line 100, 200, 200, 400, &H00ff00 draw_line 200, 400, 300, 200, &H00ff00 draw_line 300, 200, 200, 10, &H00ff00
END SUB </lang>
Vedit macro language
// Daw a line using Bresenham's line algorithm. // #1=x1, #2=y1; #3=x2, #4=y2 :DRAW_LINE: Num_Push(31,35) #31 = abs(#3-#1) // x distance #32 = abs(#4-#2) // y distance if (#4-#2 < -#31 || #3-#1 <= -#32) { #99=#1; #1=#3; #3=#99 // swap start and end points #99=#2; #2=#4; #4=#99 } if (#1 < #3) { #34=1 } else { #34=-1 } // x step if (#2 < #4) { #35=1 } else { #35=-1 } // y step if (#32 > #31) { // steep angle, step by Y #33 = #32 / 2 // error distance while (#2 <= #4) { Call("DRAW_PIXEL") #33 -= #31 if (#33 < 0) { #1 += #34 // move right #33 += #32 } #2++ // move up } } else { // not steep, step by X #33 = #31 / 2 while (#1 <= #3) { Call("DRAW_PIXEL") #33 -= #32 if (#33 < 0) { #2 += #35 // move up #33 += #31 } #1++ // move right } } Num_Pop(31,35) return