An algorithm is described for generating nonsingular affine transformations of black and white quadtrees represented as linear trees. The linear representation used, called the leafcode, is an ordered sequence of encoded BLACK leaves. The key feature of the algorithm is the fact that the output nodes are generated in traversal order, hence avoiding a final sorting step. Essentially, the algorithm proceeds for any quadrant q in the output tree as follows:
(1) If the quadrant is an output pixel (at the highest level), then it is black if the inversely transformed center of q is enclosed in a black node in the input tree.
(2) A nonpixel quadrant is black if the inversely transformed quadrant is inside an input black leaf; otherwise subdivide and recursively call for all subquadrants.
Note that both steps require some search procedure on the input tree. The paper belabors the introduction of notation, dedicating over three pages to it. The algorithm is then introduced in a more complicated than necessary Pascal notation. The results of the algorithm are compared to those of a similar algorithm by Gargantini [1,2]. The results show that the execution time of this algorithm is heavily dependent on the number of input nodes-- not surprising considering the searches on the input nodes-- while the execution of the Gargantini algorithm is more dependent on the number of output nodes. However, it is more general than the Gargantini algorithm. No attempt is made to compare the execution performance or storage requirements of this algorithm with those of pointer-based quadtrees.
