Strip trees a hierarchical representation for curves.pdf

Graphics and J. Foley Image Processing Editor Strip. Trees: A Hierarchical Representation for Curves Dana H. Ballard University of Rochester The use of curves to represent two-dimensional structures is an important part of many scientific investigations. For example, geographers use curves extensively to represent map features such as contour lines, roads, and rivers. Circuit layout designers use curves to specify the wiring between circuits. Because of the very large amount of data involved and the need to perform operations on this data efficiently, the representation of such curves is a crucial issue. A hierarchical representation consisting of binary trees with a special datum at each node is described. This datum is called a strip and the tree that contains such data is called a strip tree. Lower levels in the tree correspond to fmer resolution representations of the curve. The strip tree structure is a direct consequence of using a special method for digitizing lines and retaining all intermediate steps. This gives several desirable properties. For curves that are well-behaved, intersection and point-membership (for closed curves) calculations can be resolved in 0(log n) where n is the number of points describing the curve. The curves can be efficiently encoded and displayed at various resolutions. The representation is closed under intersection and union and these operations can be carried out at different resolutions. AH these properties depend on the hierarchical tree structure which allows primitive operations to be performed at the lowest Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and