Algorithm for converting a forest of quadtrees to a binary array

摘要

An algorithm for reconstructing a binary array of size NsxN from its forest of quadtree representation is presented. The algorithm traverses each tree of the forest in preorder and maps each ‘black’ node into the spatial domain. The time complexity in mapping is O(log N × Bn + Bp), where Bn is the number of black nodes in the forest and Bp is the number of black pixels in the N × N array. The algorithm has been implemented on an Apple II.