Digital Differential Analyzer (DDA) (Rasterization Rasterization)
Jump to navigation
Jump to search
Time Complexity
$O(n)$
Space Complexity
$O({1})$ Words
(Derived: for each iteration (i.e. each step along the line), only need to store a constant number of variables that are then overwritten in the next iteration.)
Description
"Scan-conversion line algorithm"
Approximate?
Approximate
Approximation Factor: n/a
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1983
Reference
Hearn, Baker (1997) pg. 87