| 摘要 |
An improved graphical data structure and method for processing geometrical data stored in a two-dimensional area. The invention is especially suited to storing, deleting, and conducting queries of data related to two-dimensional objects, such as the elements of a VLSI chip layout. A two-dimensional area is provided for storing a plurality of two-dimensional objects. The area may be sub-divided into a horizontal plane and a vertical plane, wherein each plane may contain one or more surfaces. Each surface typically contains a plurality of stripes of equal horizontal dimension, and the stripes are each sub-divided into sub-stripes. An object whose minimum bounding box intersects a particular sub-stripe is represented in one of four bucket lists associated with that sub-stripe. In one example of a preferred embodiment, the bucket list is selected depending upon whether the portion of the object that intersects the sub-stripe is the object's lower-left corner, left edge, bottom edge, or another portion of the object. Each bucket list is made up of a bucket list head and a number of buckets. Routines are provided for inserting objects into the graphical data structure, deleting objects from the structure, and conducting regional queries of the structure.
|
