Skip to content

Instantly share code, notes, and snippets.

@akkartik
Last active December 9, 2015 19:58
Show Gist options
  • Save akkartik/4320819 to your computer and use it in GitHub Desktop.
Save akkartik/4320819 to your computer and use it in GitHub Desktop.
Bresenham's line-drawing algorithm in my toy language.
# doesn't handle vertical lines
def (line x0 y0 x1 y1)
collect+let steep ((> abs) y1-y0 x1-x0)
when steep
swap! x0 y0
swap! x1 y1
when (x0 > x1)
swap! x0 x1
swap! y0 y1
withs (deltax x1-x0
deltay (abs y1-y0)
error deltax/2
ystep (if (y0 < y1) 1 -1)
y y0)
for x x0 (x <= x1) ++x
if steep
yield `(,y ,x)
yield `(,x ,y)
error -= deltay
when (error < 0)
y += ystep
error += deltax
# easy cases: constant coordinate changes
(test "line 0°"
:valueof (line 2 2 2 6)
:should be '((2 2) (2 3) (2 4) (2 5) (2 6)))
(test "line 45°"
:valueof (line 2 2 6 6)
:should be '((2 2) (3 3) (4 4) (5 5) (6 6)))
(test "line 135°"
:valueof (line 6 2 2 6)
:should be '((2 6) (3 5) (4 4) (5 3) (6 2)))
(test "line 180°"
:valueof (line 2 6 2 2)
:should be '((2 2) (2 3) (2 4) (2 5) (2 6)))
(test "line 225°"
:valueof (line 6 6 2 2)
:should be '((2 2) (3 3) (4 4) (5 5) (6 6)))
(test "line 315°"
:valueof (line 6 2 2 6)
:should be '((2 6) (3 5) (4 4) (5 3) (6 2)))
# harder cases
(test "line 30°"
:valueof (line 0 0 6 3)
:should be '((0 0) (1 0) (2 1) (3 1) (4 2) (5 2) (6 3)))
(test "line 60°"
:valueof (line 0 0 3 6)
:should be '((0 0) (0 1) (1 2) (1 3) (2 4) (2 5) (3 6)))
(test "line 120°"
:valueof (line 3 0 0 6)
:should be '((3 0) (3 1) (2 2) (2 3) (1 4) (1 5) (0 6)))
(test "line 150°"
:valueof (line 6 0 0 3)
:should be '((0 3) (1 3) (2 2) (3 2) (4 1) (5 1) (6 0)))
(test "line 210°"
:valueof (line 6 3 0 0)
:should be '((0 0) (1 0) (2 1) (3 1) (4 2) (5 2) (6 3)))
(test "line 240°"
:valueof (line 3 6 0 0)
:should be '((0 0) (0 1) (1 2) (1 3) (2 4) (2 5) (3 6)))
(test "line 300°"
:valueof (line 0 6 3 0)
:should be '((3 0) (3 1) (2 2) (2 3) (1 4) (1 5) (0 6)))
(test "line 330°"
:valueof (line 0 3 6 0)
:should be '((0 3) (1 3) (2 2) (3 2) (4 1) (5 1) (6 0)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment