Xiaolin Wu's line algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
Implement the Xiaolin Wu's line algorithm as described in Wikipedia. This algorithm draw antialiased lines. See Bresenham's line algorithm for aliased lines.
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>
J
Solution: <lang j> load'gl2'
coinsert'jgl2' drawpt=:4 :0"0 1
glrgb <.x*255 255 255 glpixel y )
drawLine=:3 :0 NB. drawline x1,y1,x2,y2
pts=. 2 2$y isreversed=. </ |d=. -~/pts r=.|.^:isreversed"1 pts=. /:~ pts \:"1 |d gradient=. %~/ (\:|)d
'x y'=.|:pts xpxl=.xend=. <.0.5+ x ypxl=.<.yend=. y + gradient* xend-x xgap=. -.1|x+0.5 (xgap* -.1|yend) (drawpt r)"0 2 (,:"1 +&(0 1,:0 _1)) xpxl,.ypxl
n=. >:i. <: -~/ xpxl xlist=. ({.xpxl)+n intery=. (n*gradient)+{.yend ((,.-.)1|intery) (drawpt r)"1 2 (,:+&0 1)"1 xlist,.<.intery )</lang>
Example use: Requires J6 or earlier for wd to work. <lang j> wd'pc win closeok; xywh 0 0 300 200;cc g isigraph; pas 0 0; pshow;'
glpaint drawLine 10 10 590 390</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 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>
PureBasic
<lang PureBasic>Macro PlotB(x, y, Color, b)
Plot(x, y, RGB(Red(Color) * (b), Green(Color) * (b), Blue(Color) * (b)))
EndMacro
Procedure.f fracPart(x.f)
ProcedureReturn x - Int(x)
EndProcedure
Procedure.f invFracPart(x.f)
ProcedureReturn 1.0 - fracPart(x)
EndProcedure
Procedure drawAntiAliasedLine(x1.f, y1.f, x2.f, y2.f, color)
Protected.f dx, dy, xend, yend, grad, yf, xgap, ix1, iy1, ix2, iy2 Protected x dx = x2 - x1 dy = y2 - y1 If Abs(dx) < Abs(dy) Swap x1, y1 Swap x2, y2 Swap dx, dy EndIf If x2 < x1 Swap x1, x2 Swap y1, y2 EndIf grad = dy / dx ;handle first endpoint xend = Round(x1, #pb_round_nearest) yend = y1 + grad * (xend - x1) xgap = invFracPart(x1 + 0.5) ix1 = xend ;this will be used in the MAIN loop iy1 = Int(yend) PlotB(ix1, iy1, color, invFracPart(yend) * xgap) PlotB(ix1, iy1 + 1, color, fracPart(yend) * xgap) yf = yend + grad ;first y-intersection for the MAIN loop ;handle second endpoint xend = Round(x2, #pb_round_nearest) yend = y2 + grad * (xend - x2) xgap = fracPart(x2 + 0.5) ix2 = xend ;this will be used in the MAIN loop iy2 = Int(yend) PlotB(ix2, iy2, color, invFracPart(yend) * xgap) PlotB(ix2, iy2 + 1, color, fracPart(yend) * xgap) ;MAIN loop For x = ix1 + 1 To ix2 - 1 PlotB(x, Int(yf), color, invFracPart(yf)) PlotB(x, Int(yf) + 1, color, fracPart(yf)) yf + grad Next
EndProcedure
Define w = 200, h = 200, img = 1 CreateImage(img, w, h) ;img is internal id of the image
OpenWindow(0, 0, 0, w, h,"Xiaolin Wu's line algorithm", #PB_Window_SystemMenu)
StartDrawing(ImageOutput(img))
drawAntiAliasedLine(80,20, 130,80, RGB(255, 0, 0))
StopDrawing()
ImageGadget(0, 0, 0, w, h, ImageID(img))
Define event Repeat
event = WaitWindowEvent()
Until event = #PB_Event_CloseWindow</lang>
Python
<lang python>"""Script demonstrating drawing of anti-aliased lines using Xiaolin Wu's line algorithm
usage: python xiaolinwu.py [output-file]
""" from __future__ import division import sys
from PIL import Image
def _fpart(x):
return x - int(x)
def _rfpart(x):
return 1 - _fpart(x)
def putpixel(img, xy, color, alpha=1):
"""Paints color over the background at the point xy in img. Use alpha for blending. alpha=1 means a completely opaque foreground.
""" c = tuple(map(lambda bg, fg: int(round(alpha * fg + (1-alpha) * bg)), img.getpixel(xy), color)) img.putpixel(xy, c)
def draw_line(img, p1, p2, color):
"""Draws an anti-aliased line in img from p1 to p2 with the given color.""" x1, y1, x2, y2 = p1 + p2 dx, dy = x2-x1, y2-y1 steep = abs(dx) < abs(dy) p = lambda px, py: ((px,py), (py,px))[steep]
if steep: x1, y1, x2, y2, dx, dy = y1, x1, y2, x2, dy, dx if x2 < x1: x1, x2, y1, y2 = x2, x1, y2, y1
grad = dy/dx intery = y1 + _rfpart(x1) * grad def draw_endpoint(pt): x, y = pt xend = round(x) yend = y + grad * (xend - x) xgap = _rfpart(x + 0.5) px, py = int(xend), int(yend) putpixel(img, (px, py), color, _rfpart(yend) * xgap) putpixel(img, (px, py+1), color, _fpart(yend) * xgap) return px
xstart = draw_endpoint(p(*p1)) + 1 xend = draw_endpoint(p(*p2))
for x in range(xstart, xend): y = int(intery) putpixel(img, p(x, y), color, _rfpart(intery)) putpixel(img, p(x, y+1), color, _fpart(intery)) intery += grad
if __name__ == '__main__':
if len(sys.argv) != 2: print 'usage: python xiaolinwu.py [output-file]' sys.exit(-1)
blue = (0, 0, 255) yellow = (255, 255, 0) img = Image.new("RGB", (500,500), blue) for a in range(10, 431, 60): draw_line(img, (10, 10), (490, a), yellow) draw_line(img, (10, 10), (a, 490), yellow) draw_line(img, (10, 10), (490, 490), yellow) filename = sys.argv[1] img.save(filename) print 'image saved to', filename</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>