Efficient linear quadtree construction algorithm

摘要

An algorithm for constructing a linear quadtree having a full leaf set from a raster image is investigated. This is based on methods similar to those developed by Lauzon et al.1 for handling two-dimensional run-encoded quadtrees. It examines pixels in Morton scan order, allowing the largest possible nodes to be generated in order of increasing Morton address. It has been designed for use with disc-based images and quadtrees, and is able to cope with the very large images characteristic of geographic information processing. The algorithm is compared to that of Shaffer and Samet2, and is found to be faster and to require less disc space for the output quadtree.