Xiaolin Wu's line algorithm
Implement the Xiaolin Wu's line algorithm as described in Wikipedia. This algorithm draw antialiased lines. See Bresenham's line algorithm for aliased lines.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
C
This implementation follows straightforwardly the pseudocode given on Wikipedia. (Further analysis of the code could give suggestions for improvements).
<lang c>void draw_line_antialias(
image img, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1, color_component r, color_component g, color_component b );</lang>
<lang c>inline void _dla_changebrightness(rgb_color_p from, rgb_color_p to, float br) {
if ( br > 1.0 ) br = 1.0; /* linear... Maybe something more complex could give better look */ to->red = br * (float)from->red; to->green = br * (float)from->green; to->blue = br * (float)from->blue;
}
- define plot_(X,Y,D) do{ rgb_color f_; \
f_.red = r; f_.green = g; f_.blue = b; \ _dla_plot(img, (X), (Y), &f_, (D)) ; }while(0)
inline void _dla_plot(image img, int x, int y, rgb_color_p col, float br) {
rgb_color oc; _dla_changebrightness(col, &oc, br); put_pixel_clip(img, x, y, oc.red, oc.green, oc.blue);
}
- define ipart_(X) ((int)(X))
- define round_(X) ((int)(((double)(X))+0.5))
- define fpart_(X) (((double)(X))-(double)ipart_(X))
- define rfpart_(X) (1.0-fpart_(X))
- define swap_(a, b) do{ __typeof__(a) tmp; tmp = a; a = b; b = tmp; }while(0)
void draw_line_antialias(
image img, unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, color_component r, color_component g, color_component b )
{
double dx = (double)x2 - (double)x1; double dy = (double)y2 - (double)y1; if ( fabs(dx) > fabs(dy) ) { if ( x2 < x1 ) { swap_(x1, x2); swap_(y1, y2); } double gradient = dy / dx; double xend = round_(x1); double yend = y1 + gradient*(xend - x1); double xgap = rfpart_(x1 + 0.5); int xpxl1 = xend; int ypxl1 = ipart_(yend); plot_(xpxl1, ypxl1, rfpart_(yend)*xgap); plot_(xpxl1, ypxl1+1, fpart_(yend)*xgap); double intery = yend + gradient;
xend = round_(x2); yend = y2 + gradient*(xend - x2); xgap = fpart_(x2+0.5); int xpxl2 = xend; int ypxl2 = ipart_(yend); plot_(xpxl2, ypxl2, rfpart_(yend) * xgap); plot_(xpxl2, ypxl2 + 1, fpart_(yend) * xgap);
int x; for(x=xpxl1+1; x <= (xpxl2-1); x++) { plot_(x, ipart_(intery), rfpart_(intery)); plot_(x, ipart_(intery) + 1, fpart_(intery)); intery += gradient; } } else { if ( y2 < y1 ) { swap_(x1, x2); swap_(y1, y2); } double gradient = dx / dy; double yend = round_(y1); double xend = x1 + gradient*(yend - y1); double ygap = rfpart_(y1 + 0.5); int ypxl1 = yend; int xpxl1 = ipart_(xend); plot_(xpxl1, ypxl1, rfpart_(xend)*ygap); plot_(xpxl1, ypxl1+1, fpart_(xend)*ygap); double interx = xend + gradient;
yend = round_(y2); xend = x2 + gradient*(yend - y2); ygap = fpart_(y2+0.5); int ypxl2 = yend; int xpxl2 = ipart_(xend); plot_(xpxl2, ypxl2, rfpart_(xend) * ygap); plot_(xpxl2, ypxl2 + 1, fpart_(xend) * ygap);
int y; for(y=ypxl1+1; y <= (ypxl2-1); y++) { plot_(ipart_(interx), y, rfpart_(interx)); plot_(ipart_(interx) + 1, y, fpart_(interx)); interx += gradient; } }
}
- undef swap_
- undef plot_
- undef ipart_
- undef fpart_
- undef round_
- undef rfpart_</lang>
PicoLisp
<lang PicoLisp>(scl 2)
(de plot (Img X Y C)
(set (nth Img (*/ Y 1.0) (*/ X 1.0)) (- 100 C)) )
(de ipart (X)
(* 1.0 (/ X 1.0)) )
(de iround (X)
(ipart (+ X 0.5)) )
(de fpart (X)
(% X 1.0) )
(de rfpart (X)
(- 1.0 (fpart X)) )
(de xiaolin (Img X1 Y1 X2 Y2)
(let (DX (- X2 X1) DY (- Y2 Y1)) (use (Grad Xend Yend Xgap Xpxl1 Ypxl1 Xpxl2 Ypxl2 Intery) (when (> (abs DY) (abs DX)) (xchg 'X1 'Y1 'X2 'Y2) ) (when (> X1 X2) (xchg 'X1 'X2 'Y1 'Y2) ) (setq Grad (*/ DY 1.0 DX) Xend (iround X1) Yend (+ Y1 (*/ Grad (- Xend X1) 1.0)) Xgap (rfpart (+ X1 0.5)) Xpxl1 Xend Ypxl1 (ipart Yend) ) (plot Img Xpxl1 Ypxl1 (*/ (rfpart Yend) Xgap 1.0)) (plot Img Xpxl1 (+ 1.0 Ypxl1) (*/ (fpart Yend) Xgap 1.0)) (setq Intery (+ Yend Grad) Xend (iround X2) Yend (+ Y2 (*/ Grad (- Xend X2) 1.0)) Xgap (fpart (+ X2 0.5)) Xpxl2 Xend Ypxl2 (ipart Yend) ) (plot Img Xpxl2 Ypxl2 (*/ (rfpart Yend) Xgap 1.0)) (plot Img Xpxl2 (+ 1.0 Ypxl2) (*/ (fpart Yend) Xgap 1.0)) (for (X (+ Xpxl1 1.0) (>= (- Xpxl2 1.0) X) (+ X 1.0)) (plot Img X (ipart Intery) (rfpart Intery)) (plot Img X (+ 1.0 (ipart Intery)) (fpart Intery)) (inc 'Intery Grad) ) ) ) )
(let Img (make (do 90 (link (need 120 NIL 99)))) # Create image 120 x 90
(xiaolin Img 10.0 10.0 110.0 80.0) # Draw lines (xiaolin Img 10.0 10.0 110.0 45.0) (xiaolin Img 10.0 80.0 110.0 45.0) (xiaolin Img 10.0 80.0 110.0 10.0) (out "img.pgm" # Write to bitmap file (prinl "P2") (prinl 120 " " 90) (prinl 100) (for Y Img (apply printsp Y)) ) )</lang>
Ruby
<lang ruby>def ipart(n); n.truncate; end def fpart(n); n - ipart(n); end def rfpart(n); 1.0 - fpart(n); end
class Pixmap
def draw_line_antialised(p1, p2, colour) 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 gradient = 1.0 * deltay / deltax # handle the first endpoint xend = x1.round yend = y1 + gradient * (xend - x1) xgap = rfpart(x1 + 0.5) xpxl1 = xend ypxl1 = ipart(yend) put_colour(xpxl1, ypxl1, colour, steep, rfpart(yend)*xgap) put_colour(xpxl1, ypxl1 + 1, colour, steep, fpart(yend)*xgap) itery = yend + gradient # handle the second endpoint xend = x2.round yend = y2 + gradient * (xend - x2) xgap = rfpart(x2 + 0.5) xpxl2 = xend ypxl2 = ipart(yend) put_colour(xpxl2, ypxl2, colour, steep, rfpart(yend)*xgap) put_colour(xpxl2, ypxl2 + 1, colour, steep, fpart(yend)*xgap) # in between (xpxl1 + 1).upto(xpxl2 - 1).each do |x| put_colour(x, ipart(itery), colour, steep, rfpart(itery)) put_colour(x, ipart(itery) + 1, colour, steep, fpart(itery)) itery = itery + gradient end end
def put_colour(x, y, colour, steep, c) x, y = y, x if steep self[x, y] = anti_alias(colour, self[x, y], c) end
def anti_alias(new, old, ratio) blended = new.values.zip(old.values).map {|n, o| (n*ratio + o*(1.0 - ratio)).round} RGBColour.new(*blended) end
end
bitmap = Pixmap.new(500, 500) bitmap.fill(RGBColour::BLUE) 10.step(430, 60) do |a|
bitmap.draw_line_antialised(Pixel[10, 10], Pixel[490,a], RGBColour::YELLOW) bitmap.draw_line_antialised(Pixel[10, 10], Pixel[a,490], RGBColour::YELLOW)
end bitmap.draw_line_antialised(Pixel[10, 10], Pixel[490,490], RGBColour::YELLOW)</lang>
Tcl
Uses code from Basic bitmap storage#Tcl <lang tcl>package require Tcl 8.5 package require Tk
proc ::tcl::mathfunc::ipart x {expr {int($x)}} proc ::tcl::mathfunc::fpart x {expr {$x - int($x)}} proc ::tcl::mathfunc::rfpart x {expr {1.0 - fpart($x)}}
proc drawAntialiasedLine {image colour p1 p2} {
lassign $p1 x1 y1 lassign $p2 x2 y2
set steep [expr {abs($y2 - $y1) > abs($x2 - $x1)}] if {$steep} { lassign [list $x1 $y1] y1 x1 lassign [list $x2 $y2] y2 x2 } if {$x1 > $x2} { lassign [list $x1 $x2] x2 x1 lassign [list $y1 $y2] y2 y1 } set deltax [expr {$x2 - $x1}] set deltay [expr {abs($y2 - $y1)}] set gradient [expr {1.0 * $deltay / $deltax}] # handle the first endpoint set xend [expr {round($x1)}] set yend [expr {$y1 + $gradient * ($xend - $x1)}] set xgap [expr {rfpart($x1 + 0.5)}] set xpxl1 $xend set ypxl1 [expr {ipart($yend)}] plot $image $colour $steep $xpxl1 $ypxl1 [expr {rfpart($yend)*$xgap}] plot $image $colour $steep $xpxl1 [expr {$ypxl1+1}] [expr {fpart($yend)*$xgap}] set itery [expr {$yend + $gradient}]
# handle the second endpoint set xend [expr {round($x2)}] set yend [expr {$y2 + $gradient * ($xend - $x2)}] set xgap [expr {rfpart($x2 + 0.5)}] set xpxl2 $xend set ypxl2 [expr {ipart($yend)}] plot $image $colour $steep $xpxl2 $ypxl2 [expr {rfpart($yend)*$xgap}] plot $image $colour $steep $xpxl2 [expr {$ypxl2+1}] [expr {fpart($yend)*$xgap}]
for {set x [expr {$xpxl1 + 1}]} {$x < $xpxl2} {incr x} { plot $image $colour $steep $x [expr {ipart($itery)}] [expr {rfpart($itery)}] plot $image $colour $steep $x [expr {ipart($itery) + 1}] [expr {fpart($itery)}] set itery [expr {$itery + $gradient}] }
}
proc plot {image colour steep x y c} {
set point [expr {$steep ? [list $y $x] : [list $x $y]}] set newColour [antialias $colour [getPixel $image $point] $c] setPixel $image $newColour $point
}
proc antialias {newColour oldColour c} {
# get the new colour r,g,b if {[scan $newColour "#%2x%2x%2x%c" nr ng gb -] != 3} { scan [colour2rgb $newColour] "#%2x%2x%2x" nr ng nb }
# get the current colour r,g,b scan $oldColour "#%2x%2x%2x" cr cg cb # blend the colours in the ratio defined by "c" foreach new [list $nr $ng $nb] curr [list $cr $cg $cb] { append blend [format {%02x} [expr {round($new*$c + $curr*(1.0-$c))}]] } return #$blend
}
proc colour2rgb {color_name} {
foreach part [winfo rgb . $color_name] { append colour [format %02x [expr {$part >> 8}]] } return #$colour
}
set img [newImage 500 500] fill $img blue for {set a 10} {$a < 500} {incr a 60} {
drawAntialiasedLine $img yellow {10 10} [list 490 $a] drawAntialiasedLine $img yellow {10 10} [list $a 490]
} toplevel .wu label .wu.l -image $img pack .wu.l</lang>