| 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 10:24 |
|
