CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

PDF papers
authors Samet, Hanan and Webber, Robert E.
year 1985
title Storing a Collection of Polygons Using Quadtrees
source ACM Transactions on Graphics July, 1985. vol. 4: pp. 182-222 : some ill. includes bibliography.
summary An adaptation of the quadtree data structure that represents polygonal maps (i.e., collections of polygons, possibly containing holes) is described in a manner that is also useful for the manipulation of arbitrary collections of straight line segments. The goal is to store these maps without the loss of information that results from digitization, and to obtain a worst-case execution time that is not overly sensitive to the positioning of the map. Regular decomposition variant of the region quadtree is usedÔ h)0*0*0*°° Ԍ to organize the vertices and edges of the maps. A number of related data organizations are proposed in an iterative manner until a method is obtained that meets the stated goals. The result is termed a PM (Polygonal Map) quadtree and is based on a regular decomposition Point Space quadtree (PS quadtree) that stores additional information about the edges at its terminal nodes. Algorithms are given for inserting and deleting line segments from a PM quadtree. Use of the PM quadtree to perform point location, dynamic line insertion, and map overlay is discussed. An empirical comparison of the PM quadtree with other quadtree-based representations for polygonal maps is also provided
keywords data structures, quadtree, polygons, representation, point inclusion, algorithms
series CADline
references Content-type: text/plain
last changed 2003/06/02 08:24
pick and add to favorite papersHOMELOGIN (you are user _anon_25652 from group guest) CUMINCAD Papers Powered by SciX Open Publishing Services 1.002