Intelligent and compact bucketing method for region queries in two-dimensional space
First Claim
1. Apparatus for graphically representing two-dimensional objects positioned in a flat area, comprising:
- a digital data storage unit; and
a computer operationally connected to the storage unit and programmed to generate electrical representations of a first two-dimensional surface including multiple parallel stripes dividing the surface, each stripe including two or more sub-stripes of pre-determined sizes, each sub-stripe having associated therewith a group of lists, wherein each list contains a representation of all objects intersecting the sub-stripe associated with that list in a designated manner such that each object is only represented in a single list.
3 Assignments
0 Petitions
Accused Products
Abstract
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.
-
Citations
27 Claims
-
1. Apparatus for graphically representing two-dimensional objects positioned in a flat area, comprising:
-
a digital data storage unit; and a computer operationally connected to the storage unit and programmed to generate electrical representations of a first two-dimensional surface including multiple parallel stripes dividing the surface, each stripe including two or more sub-stripes of pre-determined sizes, each sub-stripe having associated therewith a group of lists, wherein each list contains a representation of all objects intersecting the sub-stripe associated with that list in a designated manner such that each object is only represented in a single list. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method of graphically modeling objects in a flat area, comprising the steps of:
-
storing in a computer memory electrical representations of a two-dimensional surface including a plurality of uniform parallel stripes dividing the surface, wherein each stripe includes two or more sub-stripes, each sub-stripe having associated therewith a first, second, third, and fourth list; for each sub-stripe, performing steps comprising; (1) storing in the first list associated with that sub-stripe representations of all rectangular objects having edges in first and second adjacent positions that intersect the sub-stripe; (2) storing in the second list associated with that sub-stripe representations of all rectangular objects having only an edge in the second position that intersects the sub-stripe; (3) storing in the third list associated with that sub-stripe representations of all objects having only an edge in the first position that intersects the sub-stripe; (4) storing in the fourth list representations of all objects intersecting the sub-stripe that are not represented in the first, second, or third lists. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A method of graphically modeling an object in a flat area, comprising the steps of:
-
initially classifying the object as being larger in the horizontal direction or larger in the vertical direction; storing in a computer memory electrical representations of; (1) a first set of two-dimensional surfaces, wherein each surface includes a plurality of parallel horizontal stripes of uniform height dividing the surface, wherein the height of the stripes of each surface differs from the stripes of the other surfaces, and wherein each stripe includes two or more sub-stripes arranged end-to-end and each sub-stripe has associated therewith one or more lists; and (2) a second set of two-dimensional surfaces, wherein each surface includes a plurality of parallel vertical stripes of uniform width dividing the surface, wherein the width of the stripes of each surface differs from the stripes of the other surfaces, and wherein each stripe includes two or more sub-stripes arranged end-to-end and each sub-stripe has associated therewith one or more lists; in the event the object is larger in the horizontal direction, identifying the smallest stripe of the first set of surfaces that contains the object and identifying the sub-stripes of that surface that contain the object; in the event the object is larger in the vertical direction, identifying the smallest stripe of the second set of surfaces that contains the object and identifying the sub-stripes of that surface that contain the object; and storing one or more electrical representations of the object in the lists associated with the identified sub-stripes. - View Dependent Claims (19, 20, 21, 22, 23)
-
-
24. Apparatus for representing two-dimensional objects positioned in a flat area, comprising a semiconductor memory containing electrical representations of the following:
-
a first two-dimensional surface corresponding to the flat area, including multiple parallel graphical stripes of equal width extending in one orthogonal direction across the surface, each graphical stripe being subdivided into graphical sub-stripes of pre-determined sizes to form a graphical grid of rectangles; and for each sub-stripe, a group of four lists operatively associated with the sub-stripe, wherein each list stores data representative of any objects intersecting that sub-stripe in a designated manner such that each object is represented only in a single list. - View Dependent Claims (25, 26)
-
-
27. Apparatus for graphically modeling an integrated circuit or other assembly of two-dimensional area, said apparatus comprising:
-
a digital data storage unit including lists for storing data; a visual display unit; a computer functionally interconnecting the storage unit and the display unit and programmed to perform the following steps; 1) display the two-dimensional area; 2) generate a two-dimensional surface graphically representing the two-dimensional area; 3) generate a rectangular minimum bounding box for each object; 4) generate a two-dimensional graphical grid of rectangular sub-stripes on the surface; 5) position each box on the grid to correspond to the position of its respective object on the two-dimensional area; 6) for each object, record a signal in a first of a group of four lists associated with a sub-stripe that intersects two adjoining edges of the box for that object; 7) for each object, record a signal in each second of a group of four lists associated with each sub-stripe that intersects only one of the two adjoining edges of the box for that object; 8) for each object, record a signal in each third of a group of four lists associated with each sub-stripe that intersects the other of the two adjoining edges of the box for that object; 9) for each object, record a signal in each fourth of a group of four lists associated with each sub-stripe that intersects the box for that object if neither of the adjoining edges of the box intersects that sub-stripe.
-
Specification