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.
AutoHotkey
<lang AutoHotkey>#SingleInstance, Force
- NoEnv
SetBatchLines, -1
pToken := Gdip_Startup() global pBitmap := Gdip_CreateBitmap(500, 500) drawLine(100,50,400,400) Gdip_SaveBitmapToFile(pBitmap, A_ScriptDir "\linetest.png") Gdip_DisposeImage(pBitmap) Gdip_Shutdown(pToken) Run, % A_ScriptDir "\linetest.png" ExitApp
plot(x, y, c) {
A := DecToBase(255 * c, 16) Gdip_SetPixel(pBitmap, x, y, "0x" A "000000")
}
- integer part of x
ipart(x) {
return x // 1
}
rnd(x) {
return ipart(x + 0.5)
}
- fractional part of x
fpart(x) {
if (x < 0) return 1 - (x - floor(x)) return x - floor(x)
}
rfpart(x) {
return 1 - fpart(x)
}
drawLine(x0,y0,x1,y1) {
steep := abs(y1 - y0) > abs(x1 - x0) if (steep) { temp := x0, x0 := y0, y0 := temp temp := x1, x1 := y1, y1 := temp } if (x0 > x1 then) { temp := x0, x0 := x1, x1 := temp temp := y0, y0 := y1, y1 := temp } dx := x1 - x0 dy := y1 - y0 gradient := dy / dx ; handle first endpoint xend := rnd(x0) yend := y0 + gradient * (xend - x0) xgap := rfpart(x0 + 0.5) xpxl1 := xend ; this will be used in the main loop ypxl1 := ipart(yend) if (steep) { plot(ypxl1, xpxl1, rfpart(yend) * xgap) plot(ypxl1+1, xpxl1, fpart(yend) * xgap) } else { plot(xpxl1, ypxl1 , rfpart(yend) * xgap) plot(xpxl1, ypxl1+1, fpart(yend) * xgap) } intery := yend + gradient ; first y-intersection for the main loop ; handle second endpoint xend := rnd(x1) yend := y1 + gradient * (xend - x1) xgap := fpart(x1 + 0.5) xpxl2 := xend ;this will be used in the main loop ypxl2 := ipart(yend) if (steep) { plot(ypxl2 , xpxl2, rfpart(yend) * xgap) plot(ypxl2+1, xpxl2, fpart(yend) * xgap) } else { plot(xpxl2, ypxl2, rfpart(yend) * xgap) plot(xpxl2, ypxl2+1, fpart(yend) * xgap) } ; main loop while (x := xpxl1 + A_Index) < xpxl2 { if (steep) { plot(ipart(intery) , x, rfpart(intery)) plot(ipart(intery)+1, x, fpart(intery)) } else { plot(x, ipart (intery), rfpart(intery)) plot(x, ipart (intery)+1, fpart(intery)) } intery := intery + gradient }
}
DecToBase(n, Base) {
static U := A_IsUnicode ? "w" : "a" VarSetCapacity(S,65,0) DllCall("msvcrt\_i64to" U, "Int64",n, "Str",S, "Int",Base) return, S
}</lang>
BBC BASIC
<lang bbcbasic> PROCdrawAntiAliasedLine(100, 100, 600, 400, 0, 0, 0)
END DEF PROCdrawAntiAliasedLine(x1, y1, x2, y2, r%, g%, b%) LOCAL dx, dy, xend, yend, grad, yf, xgap, ix1%, iy1%, ix2%, iy2%, x% dx = x2 - x1 dy = y2 - y1 IF ABS(dx) < ABS(dy) THEN SWAP x1, y1 SWAP x2, y2 SWAP dx, dy ENDIF IF x2 < x1 THEN SWAP x1, x2 SWAP y1, y2 ENDIF grad = dy / dx xend = INT(x1 + 0.5) yend = y1 + grad * (xend - x1) xgap = xend + 0.5 - x1 ix1% = xend iy1% = INT(yend) PROCplot(ix1%, iy1%, r%, b%, g%, (INT(yend) + 1 - yend) * xgap) PROCplot(ix1%, iy1% + 1, r%, b%, g%, (yend - INT(yend)) * xgap) yf = yend + grad xend = INT(x2 + 0.5) yend = y2 + grad * (xend - x2) xgap = x2 + 0.5 - xend ix2% = xend iy2% = INT(yend) PROCplot(ix2%, iy2%, r%, b%, g%, (INT(yend) + 1 - yend) * xgap) PROCplot(ix2%, iy2% + 1, r%, b%, g%, (yend - INT(yend)) * xgap) FOR x% = ix1% + 1 TO ix2% - 1 PROCplot(x%, INT(yf), r%, b%, g%, INT(yf) + 1 - yf) PROCplot(x%, INT(yf) + 1, r%, b%, g%, yf - INT(yf)) yf += grad NEXT ENDPROC DEF PROCplot(X%, Y%, R%, G%, B%, a) LOCAL C% C% = TINT(X%*2,Y%*2) COLOUR 1, R%*a + (C% AND 255)*(1-a), \ \ G%*a + (C% >> 8 AND 255)*(1-a), \ \ B%*a + (C% >> 16 AND 255)*(1-a) GCOL 1 LINE X%*2, Y%*2, X%*2, Y%*2 ENDPROC</lang>
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>
D
This performs the mixing of the colors, both in grey scale and RGB. <lang d>import std.math, std.algorithm, grayscale_image;
/// Plots anti-aliased line by Xiaolin Wu's line algorithm. void aaLine(Color)(ref Image!Color img,
double x1, double y1, double x2, double y2, in Color color) pure nothrow @safe @nogc { // Straight translation of Wikipedia pseudocode.
// std.math.round is not pure. ** static double round(in double x) pure nothrow @safe @nogc { return floor(x + 0.5); }
static double fpart(in double x) pure nothrow @safe @nogc { return x - x.floor; }
static double rfpart(in double x) pure nothrow @safe @nogc { return 1 - fpart(x); }
auto dx = x2 - x1; auto dy = y2 - y1; immutable ax = dx.abs; immutable ay = dy.abs;
static Color mixColors(in Color c1, in Color c2, in double p) pure nothrow @safe @nogc { static if (is(Color == RGB)) return Color(cast(ubyte)(c1.r * p + c2.r * (1 - p)), cast(ubyte)(c1.g * p + c2.g * (1 - p)), cast(ubyte)(c1.b * p + c2.b * (1 - p))); else // This doesn't work for every kind of Color. return Color(cast(ubyte)(c1 * p + c2 * (1 - p))); }
// Plot function set here to handle the two cases of slope. void function(ref Image!Color, in int, in int, in double, in Color) pure nothrow @safe @nogc plot;
if (ax < ay) { swap(x1, y1); swap(x2, y2); swap(dx, dy); //plot = (img, x, y, p, col) { plot = (ref img, x, y, p, col) { assert(p >= 0.0 && p <= 1.0); img[y, x] = mixColors(col, img[y, x], p); }; } else { //plot = (img, x, y, p, col) { plot = (ref img, x, y, p, col) { assert(p >= 0.0 && p <= 1.0); img[x, y] = mixColors(col, img[x, y], p); }; }
if (x2 < x1) { swap(x1, x2); swap(y1, y2); } immutable gradient = dy / dx;
// Handle first endpoint. auto xEnd = round(x1); auto yEnd = y1 + gradient * (xEnd - x1); auto xGap = rfpart(x1 + 0.5); // This will be used in the main loop. immutable xpxl1 = cast(int)xEnd; immutable ypxl1 = cast(int)yEnd.floor; plot(img, xpxl1, ypxl1, rfpart(yEnd) * xGap, color); plot(img, xpxl1, ypxl1 + 1, fpart(yEnd) * xGap, color); // First y-intersection for the main loop. auto yInter = yEnd + gradient;
// Handle second endpoint. xEnd = round(x2); yEnd = y2 + gradient * (xEnd - x2); xGap = fpart(x2 + 0.5); // This will be used in the main loop. immutable xpxl2 = cast(int)xEnd; immutable ypxl2 = cast(int)yEnd.floor; plot(img, xpxl2, ypxl2, rfpart(yEnd) * xGap, color); plot(img, xpxl2, ypxl2 + 1, fpart(yEnd) * xGap, color);
// Main loop. foreach (immutable x; xpxl1 + 1 .. xpxl2) { plot(img, x, cast(int)yInter.floor, rfpart(yInter), color); plot(img, x, cast(int)yInter.floor + 1, fpart(yInter), color); yInter += gradient; }
}
void main() {
auto im1 = new Image!Gray(400, 300); im1.clear(Gray.white); im1.aaLine(7.4, 12.3, 307, 122.5, Gray.black); im1.aaLine(177.4, 12.3, 127, 222.5, Gray.black); im1.savePGM("xiaolin_lines1.pgm");
auto im2 = new Image!RGB(400, 300); im2.clear(RGB(0, 255, 0)); immutable red = RGB(255, 0, 0); im2.aaLine(7.4, 12.3, 307, 122.5, red); im2.aaLine(177.4, 12.3, 127, 222.5, red); im2.savePPM6("xiaolin_lines2.ppm");
}</lang>
FreeBASIC
This implementation follows the pseudocode given on Wikipedia. Only changed xend=round() in xend=ipart() to make it more in line with FreeBASIC's own line drawing routine. Rfpart give me some trouble so I changed if somewhat. The small functions where all converted into macro's <lang FreeBASIC>' version 21-06-2015 ' compile with: fbc -s console or fbc -s gui ' Xiaolin Wu’s line-drawing algorithm 'shared var and macro's
Dim Shared As UInteger wu_color
- Macro ipart(x)
Int(x) ' integer part
- EndMacro
- Macro round(x)
Int((x) + .5) ' round off
- EndMacro
- Macro fpart(x)
Frac(x) ' fractional part
- EndMacro
- Macro rfpart(x)
' 1 - Frac(x) ' seems to give problems for very small x IIf(1 - Frac(x) >= 1, 1, 1 - Frac(x))
- EndMacro
- Macro plot(x, y , c)
' use the alpha channel to set the amount of color PSet(x,y), wu_color Or (Int(c * 255)) Shl 24
- EndMacro
Sub drawline(x0 As Single, y0 As Single, x1 As Single, y1 As Single,_
col As UInteger = RGB(255,255,255))
wu_color = col And &HFFFFFF ' strip off the alpha channel information
Dim As Single gradient Dim As Single xend, yend, xgap, intery Dim As UInteger xpxl1, ypxl1, xpxl2, ypxl2, x Dim As Integer steep = Abs(y1 - y0) > Abs(x1 - x0) ' boolean
If steep Then Swap x0, y0 Swap x1, y1 End If
If x0 > x1 Then Swap x0, x1 Swap y0, y1 End If
gradient = (y1 - y0) / (x1 - x0)
' first endpoint ' xend = round(x0) xend = ipart(x0) yend = y0 + gradient * (xend - x0) xgap = rfpart(x0 + .5) xpxl1 = xend ' this will be used in the main loop ypxl1 = ipart(yend) If steep Then plot(ypxl1, xpxl1, rfpart(yend) * xgap) plot(ypxl1+1, xpxl1, fpart(yend) * xgap) Else plot(xpxl1, ypxl1, rfpart(yend) * xgap) plot(xpxl1, ypxl1+1, fpart(yend) * xgap) End If intery = yend + gradient ' first y-intersecction for the main loop
' handle second endpoint ' xend = round(x1) xend = ipart(x1) yend = y1 + gradient * (xend - x1) xgap = fpart(x1 + .5) xpxl2 = xend ' this will be used in the main loop ypxl2 = ipart(yend) If steep Then plot(ypxl2, xpxl2, rfpart(yend) * xgap) plot(ypxl2+1, xpxl2, fpart(yend) * xgap) Else plot(xpxl2, ypxl2, rfpart(yend) * xgap) plot(xpxl2, ypxl2+1, fpart(yend) * xgap) End If
' main loop If steep Then For x = xpxl1 + 1 To xpxl2 - 1 plot(ipart(intery), x, rfpart(intery)) plot(ipart(intery)+1, x, fpart(intery)) intery = intery + gradient Next Else For x = xpxl1 + 1 To xpxl2 - 1 plot(x, ipart(intery), rfpart(intery)) plot(x, ipart(intery)+1, fpart(intery)) intery = intery + gradient Next End If
End Sub
' ------=< MAIN >=------
- Define W_ 600
- Define H_ 600
- Include Once "fbgfx.bi" ' needed setting the screen attributes
Dim As Integer i Dim As String fname = __FILE__
ScreenRes W_, H_, 32,, FB.GFX_ALPHA_PRIMITIVES
Randomize Timer
For i = 0 To H_ Step H_\30
drawline(0, 0, W_, i, Int(Rnd * &HFFFFFF))
Next
For i = 0 To W_ Step W_\30
drawline(0, 0, i, H_, Int(Rnd * &HFFFFFF))
Next
i = InStr(fname,".bas") fname = Left(fname, Len(fname)-i+1) WindowTitle fname + " hit any key to end program"
While Inkey <> "" : Var _key_ = Inkey : Wend Sleep End</lang>
Go
<lang go>package raster
import "math"
func ipart(x float64) float64 {
return math.Floor(x)
}
func round(x float64) float64 {
return ipart(x + .5)
}
func fpart(x float64) float64 {
return x - ipart(x)
}
func rfpart(x float64) float64 {
return 1 - fpart(x)
}
// AaLine plots anti-aliased line by Xiaolin Wu's line algorithm. func (g *Grmap) AaLine(x1, y1, x2, y2 float64) {
// straight translation of WP pseudocode dx := x2 - x1 dy := y2 - y1 ax := dx if ax < 0 { ax = -ax } ay := dy if ay < 0 { ay = -ay } // plot function set here to handle the two cases of slope var plot func(int, int, float64) if ax < ay { x1, y1 = y1, x1 x2, y2 = y2, x2 dx, dy = dy, dx plot = func(x, y int, c float64) { g.SetPx(y, x, uint16(c*math.MaxUint16)) } } else { plot = func(x, y int, c float64) { g.SetPx(x, y, uint16(c*math.MaxUint16)) } } if x2 < x1 { x1, x2 = x2, x1 y1, y2 = y2, y1 } gradient := dy / dx
// handle first endpoint xend := round(x1) yend := y1 + gradient*(xend-x1) xgap := rfpart(x1 + .5) xpxl1 := int(xend) // this will be used in the main loop ypxl1 := int(ipart(yend)) plot(xpxl1, ypxl1, rfpart(yend)*xgap) plot(xpxl1, ypxl1+1, fpart(yend)*xgap) intery := yend + gradient // first y-intersection for the main loop
// handle second endpoint xend = round(x2) yend = y2 + gradient*(xend-x2) xgap = fpart(x2 + 0.5) xpxl2 := int(xend) // this will be used in the main loop ypxl2 := int(ipart(yend)) plot(xpxl2, ypxl2, rfpart(yend)*xgap) plot(xpxl2, ypxl2+1, fpart(yend)*xgap)
// main loop for x := xpxl1 + 1; x <= xpxl2-1; x++ { plot(x, int(ipart(intery)), rfpart(intery)) plot(x, int(ipart(intery))+1, fpart(intery)) intery = intery + gradient }
}</lang> Demonstration program: <lang go>package main
// Files required to build supporting package raster are found in: // * This task (immediately above) // * Bitmap // * Grayscale image // * Write a PPM file
import "raster"
func main() {
g := raster.NewGrmap(400, 300) g.AaLine(7.4, 12.3, 307, 122.5) g.AaLine(177.4, 12.3, 127, 222.5) g.Bitmap().WritePpmFile("wu.ppm")
}</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 xend=. <.0.5+ x yend=. y + gradient* xend-x xgap=. -.1|x+0.5
n=. i. >: -~/ xend 'xlist ylist'=. (n*/~1,gradient) + ({.xend),({.yend) weights=. ((2&}.,~ xgap*2&{.)&.(_1&|.) (,.~-.) 1|ylist) weights (drawpt r)"1 2 (,:+&0 1)"1 xlist,.<.ylist
)</lang>
Example use: <lang j> wd'pc win closeok; xywh 0 0 300 200;cc g isigraph; pas 0 0; pshow;' NB. J6 or earlier
wd'pc win closeok; minwh 600 400;cc g isidraw flush; pshow;' NB. J802 or later glpaint glclear glpaint drawLine 10 10 590 390</lang>
Liberty BASIC
<lang lb> NoMainWin WindowWidth = 270 WindowHeight = 290 UpperLeftX=int((DisplayWidth-WindowWidth)/2) UpperLeftY=int((DisplayHeight-WindowHeight)/2)
Global variablesInitialized : variablesInitialized = 0 Global BackColor$ : BackColor$ = "0 0 0" ' BackColor$ = "255 255 255"
'now, right click randomizes BG
Global size : size = 1'4 global mousepoints.mouseX0, mousepoints.mouseY0, mousepoints.mouseX1, mousepoints.mouseY1
'StyleBits #main.gbox, 0, _WS_BORDER, 0, 0 GraphicBox #main.gbox, 0, 0, 253, 252
Open "Click Twice to Form Line" For Window As #main Print #main, "TrapClose quit" Print #main.gbox, "Down; Color Black" Print #main.gbox, "Down; fill ";BackColor$ Print #main.gbox, "When leftButtonUp gBoxClick" Print #main.gbox, "When rightButtonUp RandomBG" Print #main.gbox, "Size "; size
result = drawAntiAliasedLine(126.5, 0, 126.5, 252, "255 0 0") result = drawAntiAliasedLine(0, 126, 253, 126, "255 0 0") result = drawAntiAliasedLine(0, 0, 253, 252, "255 0 0") result = drawAntiAliasedLine(253, 0, 0, 252, "255 0 0") Wait
Sub quit handle$ Close #main End End Sub
sub RandomBG handle$, MouseX, MouseY
BackColor$ = int(rnd(1)*256);" ";int(rnd(1)*256);" ";int(rnd(1)*256) Print #main.gbox, "CLS; fill ";BackColor$ variablesInitialized = 0
end sub
Sub gBoxClick handle$, MouseX, MouseY 'We will use the mousepoints "struct" to hold the values 'that way they are retained between subroutine calls If variablesInitialized = 0 Then Print #main.gbox, "CLS; fill ";BackColor$ mousepoints.mouseX0 = MouseX mousepoints.mouseY0 = MouseY variablesInitialized = 1 Else If variablesInitialized = 1 Then mousepoints.mouseX1 = MouseX mousepoints.mouseY1 = MouseY variablesInitialized = 0 result = drawAntiAliasedLine(mousepoints.mouseX0, mousepoints.mouseY0, mousepoints.mouseX1, mousepoints.mouseY1, "255 0 0") End If End If End Sub
Function Swap(Byref a,Byref b) aTemp = b b = a a = aTemp End Function
Function RoundtoInt(val) RoundtoInt = Int(val + 0.5) End Function
Function PlotAntiAliased(x, y, RGB$, b, steep)
RGB$ = Int(Val(Word$(BackColor$, 1))*(1-b) + Val(Word$(RGB$, 1)) * b) ; " " ; _ Int(Val(Word$(BackColor$, 2))*(1-b) + Val(Word$(RGB$, 3)) * b) ; " " ; _ Int(Val(Word$(BackColor$, 3))*(1-b) + Val(Word$(RGB$, 2)) * b)
if steep then 'x and y reversed Print #main.gbox, "Down; Color " + RGB$ + "; Set " + str$(y) + " " + str$(x) else Print #main.gbox, "Down; Color " + RGB$ + "; Set " + str$(x) + " " + str$(y) end if End Function
Function fracPart(x) fracPart = (x Mod 1) End function
Function invFracPart(x) invFracPart = (1 - fracPart(x)) End Function
Function drawAntiAliasedLine(x1, y1, x2, y2, RGB$) If (x2 - x1)=0 Or (y2 - y1)=0 Then Print #main.gbox, "Down; Color " + RGB$ result = BresenhamLine(x1, y1, x2, y2) Exit Function End If steep = abs(x2 - x1) < abs(y2 - y1) if steep then 'x and y should be reversed result = Swap(x1, y1) result = Swap(x2, y2) end if
If (x2 < x1) Then result = Swap(x1, x2) result = Swap(y1, y2) End If dx = (x2 - x1) dy = (y2 - y1) grad = (dy/ dx) 'Handle the First EndPoint xend = RoundtoInt(x1) yend = y1 + grad * (xend - x1) xgap = invFracPart(x1 + 0.5) ix1 = xend iy1 = Int(yend) result = PlotAntiAliased(ix1, iy1, RGB$, invFracPart(yend) * xgap, steep ) result = PlotAntiAliased(ix1, (iy1 + size), RGB$, fracPart(yend) * xgap, steep ) yf = (yend + grad) 'Handle the Second EndPoint xend = RoundtoInt(x2) yend = y2 + grad * (xend - x2) xgap = fracPart(x2 + 0.5) ix2 = xend iy2 = Int(yend) result = PlotAntiAliased(ix2, iy2, RGB$, invFracPart(yend) * xgap, steep ) result = PlotAntiAliased(ix2, (iy2 + size), RGB$, fracPart(yend) * xgap, steep ) For x = ix1 + 1 To ix2 - 1 result = PlotAntiAliased(x, Int(yf), RGB$, invFracPart(yf), steep ) result = PlotAntiAliased(x, (Int(yf) + size), RGB$, fracPart(yf), steep ) yf = (yf + grad) Next x End Function
Function BresenhamLine(x0, y0, x1, y1) dx = Abs(x1 - x0) dy = Abs(y1 - y0) sx = ((x1 > x0) + Not(x0 < x1)) sy = ((y1 > y0) + Not(y0 < y1)) errornum = (dx - dy) Do While 1 Print #main.gbox, "Set " + str$(x0) + " " + str$(y0) If (x0 = x1) And (y0 = y1) Then Exit Do errornum2 = (2 * errornum) If errornum2 > (-1 * dy) Then errornum = (errornum - dy) x0 = (x0 + sx) End If If errornum2 < dx Then errornum = (errornum + dx) y0 = (y0 + sy) End If Loop End Function
</lang>
Pascal
Based on Wikipwdia pseudocode with some optimizations and alpha handling.
<lang pascal> program wu; uses
SDL2, math;
const
FPS = 1000 div 60; SCALE = 6;
var
win: PSDL_Window; ren: PSDL_Renderer; mouse_x, mouse_y: longint; origin: TSDL_Point; event: TSDL_Event; line_alpha: byte = 255;
procedure SDL_RenderDrawWuLine(renderer: PSDL_Renderer; x1, y1, x2, y2: longint); var
r, g, b, a, a_new: Uint8; gradient, iy: real; x, y: longint; px, py: plongint;
procedure swap(var a, b: longint); var tmp: longint; begin tmp := a; a := b; b := tmp; end;
begin
if a = 0 then exit; SDL_GetRenderDrawColor(renderer, @r, @g, @b, @a); if abs(y2 - y1) > abs(x2 - x1) then begin swap(x1, y1); swap(x2, y2); px := @y; py := @x; end else begin px := @x; py := @y; end; if x1 > x2 then begin swap(x1, x2); swap(y1, y2); end; x := x2 - x1; if x = 0 then x := 1; gradient := (y2 - y1) / x; iy := y1; for x := x1 to x2 do begin a_new := round(a * frac(iy)); y := floor(iy); SDL_SetRenderDrawColor(renderer, r, g, b, a-a_new); SDL_RenderDrawPoint(renderer, px^, py^); inc(y); SDL_SetRenderDrawColor(renderer, r, g, b, a_new); SDL_RenderDrawPoint(renderer, px^, py^); iy := iy + gradient; end; SDL_SetRenderDrawColor(renderer, r, g, b, a);
end;
begin
SDL_Init(SDL_INIT_VIDEO); win := SDL_CreateWindow('Xiaolin Wus line algorithm', SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, 640, 480, SDL_WINDOW_RESIZABLE); ren := SDL_CreateRenderer(win, -1, 0); if ren = NIL then begin writeln(SDL_GetError); halt; end; SDL_SetRenderDrawBlendMode(ren, SDL_BLENDMODE_BLEND); SDL_RenderSetScale(ren, SCALE, SCALE); SDL_SetCursor(SDL_CreateSystemCursor(SDL_SYSTEM_CURSOR_CROSSHAIR));
mouse_x := 0; mouse_y := 0; origin.x := 0; origin.y := 0; repeat while SDL_PollEvent(@event) = 1 do case event.type_ of SDL_KEYDOWN: if event.key.keysym.sym = SDLK_ESCAPE then halt; SDL_MOUSEBUTTONDOWN: begin origin.x := mouse_x; origin.y := mouse_y; end; SDL_MOUSEMOTION: with event.motion do begin mouse_x := x div SCALE; mouse_y := y div SCALE; end; SDL_MOUSEWHEEL: line_alpha := EnsureRange(line_alpha + event.wheel.y * 20, 0, 255); SDL_QUITEV: halt; end;
SDL_SetRenderDrawColor(ren, 35, 35, 35, line_alpha); SDL_RenderDrawWuLine(ren, origin.x, origin.y, mouse_x, mouse_y); SDL_RenderPresent(ren); SDL_SetRenderDrawColor(ren, 255, 255, 255, 255); SDL_RenderClear(ren); SDL_Delay(FPS); until false;
end. </lang>
Perl
This is mostly a translation of the pseudo-code on Wikipedia, except that the $plot trick was inspired by the perl6 RosettaCode example. <lang perl>#!perl use strict; use warnings;
sub plot { my ($x, $y, $c) = @_; printf "plot %d %d %.1f\n", $x, $y, $c if $c; }
sub ipart { int shift; }
sub round { int( 0.5 + shift ); }
sub fpart { my $x = shift; $x - int $x; }
sub rfpart { 1 - fpart(shift); }
sub drawLine { my ($x0, $y0, $x1, $y1) = @_;
my $plot = \&plot;
if( abs($y1 - $y0) > abs($x1 - $x0) ) { $plot = sub { plot( @_[1, 0, 2] ) }; ($x0, $y0, $x1, $y1) = ($y0, $x0, $y1, $x1); }
if( $x0 > $x1 ) { ($x0, $x1, $y0, $y1) = ($x1, $x0, $y1, $y0); }
my $dx = $x1 - $x0; my $dy = $y1 - $y0; my $gradient = $dy / $dx;
my @xends; my $intery;
# handle the endpoints for my $xy ([$x0, $y0], [$x1, $y1]) { my ($x, $y) = @$xy; my $xend = round($x); my $yend = $y + $gradient * ($xend - $x); my $xgap = rfpart($x + 0.5);
my $x_pixel = $xend; my $y_pixel = ipart($yend); push @xends, $x_pixel;
$plot->($x_pixel, $y_pixel , rfpart($yend) * $xgap); $plot->($x_pixel, $y_pixel+1, fpart($yend) * $xgap); next if defined $intery; # first y-intersection for the main loop $intery = $yend + $gradient; }
# main loop
for my $x ( $xends[0] + 1 .. $xends[1] - 1 ) { $plot->($x, ipart ($intery), rfpart($intery)); $plot->($x, ipart ($intery)+1, fpart($intery)); $intery += $gradient; } }
if( $0 eq __FILE__ ) { drawLine( 0, 1, 10, 2 ); } __END__ </lang>
- Output:
plot 0 1 0.5 plot 10 2 0.5 plot 1 1 0.9 plot 1 2 0.1 plot 2 1 0.8 plot 2 2 0.2 plot 3 1 0.7 plot 3 2 0.3 plot 4 1 0.6 plot 4 2 0.4 plot 5 1 0.5 plot 5 2 0.5 plot 6 1 0.4 plot 6 2 0.6 plot 7 1 0.3 plot 7 2 0.7 plot 8 1 0.2 plot 8 2 0.8 plot 9 1 0.1 plot 9 2 0.9
Perl 6
<lang perl6>sub plot(\x, \y, \c) { say "plot {x} {y} {c}" }
sub fpart(\x) { x - floor(x) }
sub draw-line(@a is copy, @b is copy) {
my Bool \steep = abs(@b[1] - @a[1]) > abs(@b[0] - @a[0]); my $plot = &OUTER::plot; if steep {
$plot = -> $y, $x, $c { plot($x, $y, $c) } @a.=reverse; @b.=reverse;
} if @a[0] > @b[0] { my @t = @a; @a = @b; @b = @t }
my (\x0,\y0) = @a; my (\x1,\y1) = @b; my \dx = x1 - x0; my \dy = y1 - y0; my \gradient = dy / dx; # handle first endpoint my \x-end1 = round(x0); my \y-end1 = y0 + gradient * (x-end1 - x0); my \x-gap1 = 1 - round(x0 + 0.5);
my \x-pxl1 = x-end1; # this will be used in the main loop my \y-pxl1 = floor(y-end1); my \c1 = fpart(y-end1) * x-gap1;
$plot(x-pxl1, y-pxl1 , 1 - c1) unless c1 == 1; $plot(x-pxl1, y-pxl1 + 1, c1 ) unless c1 == 0; # handle second endpoint my \x-end2 = round(x1); my \y-end2 = y1 + gradient * (x-end2 - x1); my \x-gap2 = fpart(x1 + 0.5);
my \x-pxl2 = x-end2; # this will be used in the main loop my \y-pxl2 = floor(y-end2); my \c2 = fpart(y-end2) * x-gap2; my \intery = y-end1 + gradient;
# main loop for (x-pxl1 + 1 .. x-pxl2 - 1)
Z (intery, intery + gradient ... *)
-> \x,\y {
my \c = fpart(y); $plot(x, floor(y) , 1 - c) unless c == 1; $plot(x, floor(y) + 1, c ) unless c == 0;
}
$plot(x-pxl2, y-pxl2 , 1 - c2) unless c2 == 1; $plot(x-pxl2, y-pxl2 + 1, c2 ) unless c2 == 0;
}
draw-line [0,1], [10,2];</lang>
- Output:
plot 0 1 1 plot 1 1 0.9 plot 1 2 0.1 plot 2 1 0.8 plot 2 2 0.2 plot 3 1 0.7 plot 3 2 0.3 plot 4 1 0.6 plot 4 2 0.4 plot 5 1 0.5 plot 5 2 0.5 plot 6 1 0.4 plot 6 2 0.6 plot 7 1 0.3 plot 7 2 0.7 plot 8 1 0.2 plot 8 2 0.8 plot 9 1 0.1 plot 9 2 0.9 plot 10 2 1
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>
Racket
<lang racket>#lang racket (require 2htdp/image)
(define (plot img x y c)
(define c*255 (exact-round (* (- 1 c) 255))) (place-image (rectangle 1 1 'solid (make-color c*255 c*255 c*255 255)) x y img))
(define ipart exact-floor) ; assume that a "round-down" is what we want when -ve
- `round` is built in -- but we'll use exact round (and I'm not keen on over-binding round)
(define (fpart n) (- n (exact-floor n))) (define (rfpart n) (- 1 (fpart n)))
(define (draw-line img x0 y0 x1 y1)
(define (draw-line-steeped img x0 y0 x1 y1 steep?) (define (draw-line-steeped-l-to-r img x0 y0 x1 y1 steep?) (define dx (- x1 x0)) (define dy (- y1 y0)) (define gradient (/ dy dx)) (define (handle-end-point img x y) (define xend (exact-round x)) (define yend (+ y (* gradient (- xend x)))) (define xgap (rfpart (+ x 0.5))) (define ypxl (ipart yend)) (define intery (+ yend gradient)) (case steep? [(#t) (define img* (plot img ypxl xend (* xgap (rfpart yend)))) (values (plot img* (+ ypxl 1) xend (* xgap (fpart yend))) xend intery)] [(#f) (define img* (plot img xend ypxl (* xgap (rfpart yend)))) (values (plot img* xend (+ ypxl 1) (* xgap (fpart yend))) xend intery)])) (define-values (img-with-l-endpoint xpl1 intery) (handle-end-point img x0 y0)) (define-values (img-with-r-endpoint xpl2 _) (handle-end-point img-with-l-endpoint x1 y1)) (for/fold ((img img-with-l-endpoint) (y intery)) ((x (in-range (+ xpl1 1) xpl2))) (define y-i (ipart y)) (values (case steep? [(#t) (define img* (plot img y-i x (rfpart y))) (plot img* (+ 1 y-i) x (fpart y))] [(#f) (define img* (plot img x y-i (rfpart y))) (plot img* x (+ 1 y-i) (fpart y))]) (+ y gradient)))) (if (> x0 x1) (draw-line-steeped-l-to-r img x1 y1 x0 y0 steep?) (draw-line-steeped-l-to-r img x0 y0 x1 y1 steep?))) (define steep? (> (abs (- y1 y0)) (abs (- x1 x0)))) (define-values (img* _) (if steep? (draw-line-steeped img y0 x0 y1 x1 steep?) (draw-line-steeped img x0 y0 x1 y1 steep?))) img*)
(define img-1 (beside
(scale 3 (draw-line (empty-scene 150 100) 12 12 138 88)) (above (scale 1 (draw-line (empty-scene 150 100) 12 50 138 50)) (scale 1 (draw-line (empty-scene 150 100) 75 12 75 88)) (scale 1 (draw-line (empty-scene 150 100) 12 88 138 12)))))
(define img-2
(beside (scale 3 (draw-line (empty-scene 100 150) 12 12 88 138)) (above (scale 1 (draw-line (empty-scene 100 150) 50 12 50 138)) (scale 1 (draw-line (empty-scene 100 150) 12 75 88 75)) (scale 1 (draw-line (empty-scene 100 150) 88 12 12 138)))))
img-1 img-2 (save-image img-1 "images/xiaolin-wu-racket-1.png") (save-image img-2 "images/xiaolin-wu-racket-2.png")</lang>
Output files: File:Xiaolin-wu-racket-1.png File:Xiaolin-wu-racket-2.png
REXX
This REXX example uses the Xiaolin Wu line algorithm to draw a line (with output).
Apparently, there may be an error in the definition of the algorithm (which only manifests itself with negative numbers):
use of the IPART function should probably be FLOOR.
[See the talk section on the Xiaolin Wu's line algorithm.]
http://en.wikipedia.org/wiki/Talk:Xiaolin_Wu%27s_line_algorithm
Also, it takes in account (that can easily be overlooked) of the note after the description of the algorithm:
Note: If at the beginning of the routine abs(dx) < abs(dy) is true, then all plotting should be done with x and y reversed.
<lang rexx>/*REXX program plots/draws a line using the Xiaolin Wu line algorithm.*/
background = 'fa'x /*background char: middle-dot. */
image. = background /*fill the array with middle-dots*/ plotC = '░▒▓█' /*chars used for plotting points.*/ EoE = 1000 /*EOE = End Of Earth, er... plot.*/ do j=-EoE to +EoE /*draw grid from lowest──►highest*/ image.j.0 = '─' /*draw the horizontal axis. */ image.0.j = '│' /* " " verical " */ end /*j*/
image.0.0 = '┼' /*"draw" the axis origin (char). */ parse arg xi yi xf yf . /*allow specifying line-end pts. */ if xi== | xi==',' then xi = 1 /*if not specified, use default. */ if yi== | yi==',' then yi = 2 /* " " " " " */ if xf== | xf==',' then xf = 11 /* " " " " " */ if yf== | yf==',' then yf = 12 /* " " " " " */ minX=0; minY=0 /*used as limits for plotting. */ maxX=0; maxY=0 /* " " " " " */ call line_draw xi, yi, xf, yf /*call subroutine and draw line. */ border = 2 /*allow additional space for plot*/ minX=minX-border*2; maxX=maxX+border*2 minY=minY-border ; maxY=maxY+border
do y=maxY by -1 to minY; _= /*build a row*/ do x=minX to maxX _=_ || image.x.y end /*x*/ say _ /*display row*/ end /*y*/
exit /*stick a fork in it, we're done.*/ /*────────────────────────────────DRAW_LINE subroutine──────────────────*/ line_draw: procedure expose background image. minX maxX minY maxY plotC parse arg x1, y1, x2, y2; switchXY=0; dx=x2-x1
dy=y2-y1
if abs(dx)<abs(dy) then do
parse value x1 y1 with y1 x1 /*swap x1 & y1*/ parse value x2 y2 with y2 x2 /*swap x2 & y2*/ parse value dx dy with dy dx /*swap dx & dy*/ end
if x2<x1 then do
parse value x1 x2 with x2 x1 /*swap x1 & x2*/ parse value y1 y2 with y2 y1 /*swap y1 & y2*/ switchXY=1 end
gradient = dy/dx
xend = round(x1) /*────1st endpoint────────────────────*/ yend = y1 + gradient * (xend-x1) intery = yend + gradient xgap = 1 - fpart(x1+.5) xpx11 = xend; ypx11 = floor(yend); ypx11_=ypx11+1
call plotXY xpx11, ypx11, brite(1-fpart(yend*xgap)),switchXY call plotXY xpx11, ypx11_, brite( fpart(yend*xgap)),switchXY
xend = round(x2) /*────2nd endpoint────────────────────*/ yend = y2 + gradient * (xend-x2) xgap = fpart(x2+.5) xpx12 = xend; ypx12 = floor(yend); ypx12_=ypx12+1
call plotXY xpx12, ypx12, brite(1-fpart(yend*xgap)), switchXY call plotXY xpx12, ypx12_, brite( fpart(yend*xgap)), switchXY
do x=xpx11+1 to xpx12-1 /*────draw the line───────────────────*/ !intery = floor(intery) !intery_ = !intery+1 call plotXY x, !intery, brite(1-fpart(intery)), switchXY call plotXY x, !intery_, brite( fpart(intery)), switchXY intery = intery + gradient end /*x*/
return /*────────────────────────────────BRITE subroutine──────────────────────*/ brite: procedure expose background plotC; parse arg p return substr(background || plotC, 1+round(abs(p)*length(plotC)), 1) /*────────────────────────────────PLOTXY subroutine─────────────────────*/ plotXY: procedure expose image. minX maxX minY maxY parse arg xx, yy, bc, switchYX; if switchYX then parse arg yy, xx image.xx.yy=bc; minX=min(minX,xx); maxX=max(maxX,xx)
minY=min(minY,yy); maxY=max(maxY,yy)
return /*────────────────────────────────FLOOR subroutine──────────────────────*/ floor: procedure; parse arg ?; _=trunc(?); return _-(?<0)*(?\=_) /*────────────────────────────────FPART subroutine──────────────────────*/ fpart: procedure; parse arg ?; return abs(?-trunc(?)) /*────────────────────────────────ROUND subroutine─────────arg2 is place*/ round: return format(arg(1), , word(arg(2) 0, 1))</lang> output when using the default input
····│··············· ····│··············· ····│··············· ····│··········█···· ····│·········█····· ····│········█······ ····│·······█······· ····│······█········ ····│·····█········· ····│····█·········· ····│···█··········· ····│··█············ ····│·█············· ····│█·············· ····│··············· ────┼─────────────── ····│··············· ····│···············
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>
Scala
Uses Bitmap#Scala. <lang Scala>import java.awt.Color import math.{floor => ipart, round, abs}
case class Point(x: Double, y: Double) {def swap = Point(y, x)}
def plotter(bm: RgbBitmap, c: Color)(x: Double, y: Double, v: Double) = {
val X = round(x).toInt val Y = round(y).toInt val V = v.toFloat // tint the existing pixels val c1 = c.getRGBColorComponents(null) val c2 = bm.getPixel(X, Y).getRGBColorComponents(null) val c3 = (c1 zip c2).map{case (n, o) => n * V + o * (1 - V)} bm.setPixel(X, Y, new Color(c3(0), c3(1), c3(2)))
}
def drawLine(plotter: (Double,Double,Double) => _)(p1: Point, p2: Point) {
def fpart(x: Double) = x - ipart(x) def rfpart(x: Double) = 1 - fpart(x) def avg(a: Float, b: Float) = (a + b) / 2
val steep = abs(p2.y - p1.y) > abs(p2.x - p1.x) val (p3, p4) = if (steep) (p1.swap, p2.swap) else (p1, p2) val (a, b) = if (p3.x > p4.x) (p4, p3) else (p3, p4) val dx = b.x - a.x val dy = b.y - a.y val gradient = dy / dx var intery = 0.0
def endpoint(xpxl: Double, yend: Double, xgap: Double) { val ypxl = ipart(yend) if (steep) { plotter(ypxl, xpxl, rfpart(yend) * xgap) plotter(ypxl+1, xpxl, fpart(yend) * xgap) } else { plotter(xpxl, ypxl , rfpart(yend) * xgap) plotter(xpxl, ypxl+1, fpart(yend) * xgap) } }
// handle first endpoint var xpxl1 = round(a.x); { val yend = a.y + gradient * (xpxl1 - a.x) val xgap = rfpart(a.x + 0.5) endpoint(xpxl1, yend, xgap) intery = yend + gradient }
// handle second endpoint val xpxl2 = round(b.x); { val yend = b.y + gradient * (xpxl2 - b.x) val xgap = fpart(b.x + 0.5) endpoint(xpxl2, yend, xgap) }
// main loop for (x <- (xpxl1 + 1) to (xpxl2 - 1)) { if (steep) { plotter(ipart(intery) , x, rfpart(intery)) plotter(ipart(intery)+1, x, fpart(intery)) } else { plotter(x, ipart (intery), rfpart(intery)) plotter(x, ipart (intery)+1, fpart(intery)) } intery = intery + gradient }
}</lang> Example:
Test line drawing in various directions including vertical, horizontal, 45° and oblique (such lines are drawn multiple times to test swapped parameters). <lang Scala>val r = 120 val img = new RgbBitmap(r*2+1, r*2+1) val line = drawLine(plotter(img, Color.GRAY)_)_ img.fill(Color.WHITE) for (angle <- 0 to 360 by 30; θ = math toRadians angle; θ2 = θ + math.Pi) {
val a = Point(r + r * math.sin(θ), r + r * math.cos(θ)) val b = Point(r + r * math.sin(θ2), r + r * math.cos(θ2)) line(a, b)
} javax.imageio.ImageIO.write(img.image, "png", new java.io.File("XiaolinWuLineAlgorithm.png"))</lang>
- Output:
View the PNG, available at the following URL because RosettaCode image uploads were disabled: https://lh5.googleusercontent.com/GxBAHV4nebuO1uiKboKc6nQmmtlJV47jPwVZnQHcbV7TKm0kjdKfKteclCfxmSdFJnSKvYYoB5I
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>