The Best-Fit DDA Algorithm
The Best-Fit DDA Algorithm
The Best-Fit DDA is an algorithm for converting a segment into a nice-looking sequence of pixels. The conversion of a segment from to with involves a sequence of steps. At each step the segment is approximated by the concatenation of copies of a path with copies of a path . Initially, =x-y, =y, ={0} (a single horizontal increment), and ={1} (a diagonal increment). Update: if > then ←-, ←join(reverse(),), else ←-, ←join(reverse(),). The algorithm terminates when =0.
(0,0)
(x,y)
x>y
n
1
p
1
n
2
p
2
n
1
n
2
p
1
p
2
n
1
n
2
n
1
n
1
n
2
p
2
p
2
p
1
n
2
n
2
n
1
p
1
p
1
p
2
n
2