Premium
A Run‐Length Slice Line Drawing Algorithm without Division Operations
Author(s) -
Fung Khun Yee,
Nicholl Tina M.,
Dewdney A. K.
Publication year - 1992
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.1130267
Subject(s) - initialization , division (mathematics) , algorithm , computer science , line (geometry) , division algorithm , reduction (mathematics) , line segment , arithmetic , mathematics , artificial intelligence , geometry , programming language
Of the two major approaches to line drawing, run‐length slice algorithms are seldom used because of the division operation deemed necessary in these algorithms. The biggest advantage of these algorithms, the reduction of additions used, is considered outweighed by the division used. In this paper, a new run‐length slice algorithm that does not require a division operation is presented. Furthermore, it uses the double‐stepping paradigm in incremental line drawing algorithms to reduce the number of additions used by at least half. For sufficiently long lines, this algorithm uses at least 50% fewer arithmetic operations than Wu et al.'s bi‐directional double‐step incremental algorithm. But because of its high initialization cost, for short lines, it is less efficient. For a line with endpoints (0,0) and (δx, δy), the strategy is then to use the bi‐directional Bresenham algorithm for very short lines (δx < 20), the bi‐directional double‐step algorithm for moderate long lines (20 ≤δx ≤ 110), and the new algorithmfor the longer lines (δx > 110).