Back to results
US 6,701,306 B1Granted
Methods and apparatus for manipulating polygons in a multidimensional space
AssigneeCadence Design Systems, Inc.
InventorsTom Kronmiller, Steven Teig
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneeCadence Design Systems, Inc.
InventorsTom Kronmiller, Steven Teig
Estimating the term…
Geometric objects, such as polygons, are defined in a multi-dimensional data space. The geometric objects are represented by data segments for processing in a computer. “N” dimensional hierarchical trees, or “ng” trees, are generated to organize the data segments into “outside child nodes” and “inside child nodes” in accordance with a discriminator value. The discriminator value is selected for each layer or discriminator dimension in the ng tree. For the ng tree, one of “n” sides of a polygon is selected as the discriminator value. To create the ng tree, data segments are designated as “outside child nodes” if a data segment is outside the plane defined by the discriminator value, and data segments are selected as “inside child nodes” if the data segment is inside the plane defined by the discriminator value. This process of partitioning data segments into inside child nodes and outside child nodes is repeated recursively through each level of the ng tree. The ng tree has application to represent diagonal interconnect lines of regions defined in a multidimensional design layout of an integrated circuit.
A method for storing data in a computer to represent a plurality of “n” sided geometric objects, said method comprising the steps of:
A computer readable medium comprising a plurality of instructions for storing data in a computer to represent a plurality of “n” sided geometric objects, said instructions, when executed by a computer, cause the computer to perform the steps of:
Dependencies are inferred from the claim text.