Methods and apparatus for manipulating polygons in a multidimensional space

• US 6,701,306 B1
• Filed: 01/31/2002
• Issued: 03/02/2004
• Est. Priority Date: 03/15/2000
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Kronmiller, Tom
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US10/061,447
• Time in Patent Office: 761 Days
• Field of Search: 707/2, 707/3, 707/101, 707/102, 707/103.R, 707/10, 706/11, 704/236, 701/209, 715/503
• US Class Current: 707/797
• CPC Class Codes: B60T 2210/36 Global Positioning System [GPS]
• CPC Class Codes: B60T 2250/04 Vehicle reference speed; Vehicle body speed
• CPC Class Codes: B60T 8/172 Determining control parameters used in the regulation, e.g. by calculations involving measured or detected parameters B60T8/17551 takes precedence
• CPC Class Codes: G01P 13/02 Indicating direction only, e.g. by weather vane
• CPC Class Codes: G01P 7/00 Measuring speed by integrating acceleration measuring travelled distance by double integration of acceleration G01C21/16
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

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.

Claims

1. A method for storing data in a computer to represent a plurality of “

n”

sided geometric objects, said method comprising the steps of;

generating segment data for each of a plurality of, “

n”

sided geometric objects, said segment data specifying “

n”

number of sides and including “

n”

vertices for a corresponding geometric object;

generating a hierarchical tree, with k levels of nodes, to represent said “

n”

sided geometric objects, wherein each node is associated with one of said segment data, by;

selecting a discriminating node as a parent node for a corresponding level;

computing a discriminator dimension;

selecting one of said “

n”

vertices based on said discriminator dimension for said discriminating node for use as a discriminator key for each of said k levels; and

portioning nodes, not yet assigned to said hierarchical tree, into outside_child nodes and inside_child nodes based on a comparison between said discriminator key and segment data for a node under analysis and recursively portioning nodes into said outside_child nodes and said inside_child nodes for each of said k levels.

2. The method as set forth in claim 1, wherein the step of selecting a discriminating key for each of said k levels comprises the step of computing said discriminator dimension to equal k modulo the number of sides in said discriminating geometric object.

3. The method as set forth in claim 1, further comprising the steps of:

defining a plurality of data regions in a multidimensional data space that encompasses said geometric objects; and

generating a plurality of hierarchical data structures for a number of said data regions, wherein each hierarchical data structure corresponds to a particular data region and stores hierarchical trees for geometric objects within its particular data region.

4. The method as set forth in claim 3, further comprising the steps of:

storing said hierarchical data structures in a first memory of a computer system;

retrieving said hierarchical data structure of a data region from the first memory;

storing said hierarchical data structure in a second memory of the computer system; and

performing a query on said hierarchical data structure.

5. The method of claim 3, further comprising the step of creating a hierarchical data structure for each data region.

6. The method of claim 3, further comprising the step of creating hierarchical data structures for all data regions that contain geometric objects.

7. The method of claim 3, further comprising the step of adaptively determining the number or size of the data regions in the multidimensional data space based on the number of geometric objects in the multidimensional space.

8. The method of claim 1, wherein said geometric objects represent diagonal interconnect lines in a design layout of an integrated circuit, wherein a diagonal interconnect line defines a line deposed in a direction other than zero or ninety degrees relative to the integrated circuit boundaries.

9. The method of claim 3, further comprising:

for each particular region that has a hierarchical data structure,

a) identifying geometric objects outside of the particular region that are needed for the analysis of the geometric objects within the particular region; and

b) inserting the segment data of the identified geometric objects into the hierarchical data structure for the particular region.

10. The method of claim 3, wherein a particular geometric object crosses a boundary between a first region and a second region, wherein a first portion of the geometric object is in the first region, the method further comprising:

a) defining first segment data to represent the first portion; and

b) inserting the first segment data into the hierarchical data structure of the first region.

11. The method of claim 10, wherein the step of defining a first segment data to represent the first portion comprises the steps of:

defining a smallest axes-rectangle that encompasses said geometric object; and

using said rectangle as said first segment data.

12. 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;

generating segment data for each of a plurality of “

n”

sided geometric objects, said segment data specifying “

n”

number of sides and including “

n”

vertices for a corresponding geometric object;

generating a hierarchical tree, with k levels of nodes, to represent said “

n”

sided geometric objects, wherein each node is associated with one of said segment data, by;

selecting a discriminating node as a parent node for a corresponding level;

computing a discriminator dimension;

selecting one of said “

n”

vertices based on said discriminator dimension for said discriminating node for use as a discriminator key for each of said k levels; and

portioning nodes, not yet assigned to said hierarchical tree, into outside_child nodes and inside_child nodes based on a comparison between said discriminator key and segment data for a node under analysis and recursively portioning nodes into said outside_child nodes and said inside child nodes for each of said k levels.

13. The computer readable medium as set forth in claim 12, wherein the step of selecting a discriminating key for each of said k levels comprises the step of computing said discriminator dimension to equal k modulo the number of sides in said discriminating geometric object.

14. The computer readable medium as set forth in claim 12, further comprising the steps of:

defining a plurality of data regions in a multidimensional data space that encompasses said geometric objects; and

generating a plurality of hierarchical data structures for a number of said data regions, wherein each hierarchical data structure corresponds to a particular data region and stores hierarchical trees for geometric objects within its particular data region.

15. The computer readable medium as set forth in claim 14, further comprising the steps of:

storing said hierarchical data structures in a first memory of a computer system;

retrieving said hierarchical data structure of a data region from the first memory;

storing said hierarchical data structure in a second memory of the computer system; and

performing a query on said hierarchical data structure.

16. The computer readable, medium of claim 14, further comprising the step of creating a hierarchical data structure for each data region.

17. The computer readable medium of claim 14, further comprising the step of creating hierarchical data structures for all data regions that contain geometric objects.

18. The computer readable medium of claim 14, further comprising the step of adaptively determining the number or size of the data regions in the multidimensional data space based on the number of geometric objects in the multidimensional space.

19. The computer readable medium of claim 12, wherein said geometric objects represent diagonal interconnect lines in a design layout of an integrated circuit, wherein a diagonal interconnect line defines a line deposed in a direction other than zero or ninety degrees relative to the integrated circuit boundaries.

20. The computer readable medium of claim 14, further comprising:

for each particular region that has a hierarchical data structure,

a) identifying geometric objects outside of the particular region that are needed for the analysis of the geometric objects within the particular region; and

b) inserting the segment data of the identified geometric objects into the hierarchical data structure for the particular region.

21. The computer readable medium of claim 14, wherein a particular geometric object crosses a boundary between a first region and a second region, wherein a first portion of the geometric object is in the first region, the method further comprising:

a) defining first segment data to represent the first portion; and

b) inserting the first segment data into the hierarchical data structure of the first region.

22. The computer readable medium of claim 21, wherein the step of defining a first segment data to represent the first portion comprises the steps of:

defining a smallest axes-rectangle that encompasses said geometric object; and

using said rectangle as said first segment data.