Bitmap/Bresenham's line algorithm: Difference between revisions
< Bitmap
Content added Content deleted
(added C) |
(Ada solution added) |
||
Line 3: | Line 3: | ||
Using the data storage type defined [[Basic_bitmap_storage|on this page]] for raster graphics images, draw a line given 2 points with the Bresenham's algorithm ([http://en.wikipedia.org/wiki/Bresenham's_line_algorithm definition on Wikipedia]). |
Using the data storage type defined [[Basic_bitmap_storage|on this page]] for raster graphics images, draw a line given 2 points with the Bresenham's algorithm ([http://en.wikipedia.org/wiki/Bresenham's_line_algorithm definition on Wikipedia]). |
||
=={{header|Ada}}== |
|||
<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_Y; |
|||
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; |
|||
</ada> |
|||
The test program's |
|||
<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); |
|||
</ada> |
|||
sample output |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
Line 46: | Line 119: | ||
#undef swap_uint |
#undef swap_uint |
||
#undef plot</C> |
#undef plot</C> |
||
=={{header|MAXScript}}== |
=={{header|MAXScript}}== |
Revision as of 13:38, 6 December 2008
Bitmap/Bresenham's line algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
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 (definition on Wikipedia).
Ada
<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_Y; 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; </ada> The test program's <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);
</ada> 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
C
<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</C>
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
<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
- </ocaml>