Patent ID: 7389001
Filing Date: 2008-06-17
Classification: G06F

Abstract:
1. A method comprising: scanning a layer of a layout across one or more hierarchical levels of the layout in a first direction and selecting a first rectangle in a scan order; scanning the layer of the layout in a second direction orthogonal to the first direction to find a second rectangle that intersects the first rectangle; and if the second rectangle is found, performing a union of the first and second rectangles to generate a set of non-intersecting rectangles equivalent to the first and second rectangle; storing the first rectangle in an output store if no rectangle that intersects the first rectangle is found; wherein scanning a layer of a layout in a first direction and selecting a first rectangle in a scan order further comprises storing points of rectangles on the layer of the layout in a first data structure of points in an order based at least in part on the relative horizontal positions of the rectangles formed by the points in the layout; and extracting a point of a first rectangle from the first data structure, the point being the least in order in the first data structure; and wherein scanning the layer of the layout in a second direction orthogonal to the first direction for a second rectangle that intersects the first rectangle further comprises: reinserting at least the vertical coordinate of the extracted point from the first rectangle into a second data structure, organized in an order based at least in part on the relative vertical positions of the rectangles formed by the points in the layout; and examining each rectangle vertically adjacent to the extracted rectangle in a pair wise fashion with reference to the first rectangle by traversing the second data structure.