Algorithms for the Conversion of Quadtrees to Rasters

A number of algorithms are presented for obtaining a raster representation for an image given its quadtree. The algorithms are given in an evolutionary manner starting with the straight-forward top-down approach that visits each run in a row in succession starting at the root of the tree. The remaining algorithms proceed in a manner akin to an inorder tree traversal. All of the algorithms are analyzed and an indication is given as to when each is preferable. The execution time of all of the algorithms is shown to be proportional to the sum of the heights of the blocks comprising the image.