Region Representation: Quadtrees from Boundary Codes

摘要

An algorithm is presented for constructing a quadtree for a region given its boundary in the form of a chain code. The algorithm makes use of some geometrical properties of the region to enable the detection of the maximal size blocks of the region without actually visiting all of the subblocks of the maximal size block. Analysis of the algorithm reveals that its execution time is proportional to the product of the perimeter and the log of the diameter of the region. (Author)