A General PASCAL Program for Map Overlay of Quadtrees and Related Problems
F. Warren Burton · The Computer Journal · 1987
A simple but general map overlay function is defined for quadtrees. It is shown that many common quadtree operations, including union, intersection, relative complement, masking, copy, complement and generalisation of quadtrees, can all be viewed as special cases of map overlay, depending on how pixel values of the result of an overlay are determined from the corresponding pixels of the maps being overlaid. It is shown that some operations, such as union, can be more efficiently performed by specialised algorithms. A more general overlay function is given, which is optimal (to within a constant factor) with respect to both time and space for all of the above operations. This overlay function requires two functions as parameters. One function determines when the quadtrees being overlaid are simple enough to be processed without further subdivision. The other performsthe overlay for simple cases.