A method of comparing two rectangles of a circuit design structure for overlap
is provided. The two rectangles being compared are modified conceptually in such
a way as to reduce the amount of computation necessary to determine if the two
rectangles overlap. In one embodiment, a first rectangle is reduced in both x-
and y-directions to a single point residing in the center of that rectangle, while
the size of the second rectangle is expanded in both x- and y-directions by the
same amount, resulting in an enlarged rectangle. A determination of whether the
single point resides within the enlarged rectangle thus indicates if the two original
rectangles overlap. Similarly, in another embodiment, a first rectangle is reduced
in the x-direction only, resulting in a y-directed line segment, while a second
rectangle is reduced in the y-direction, resulting in an x-directed line segment.
The y-directed line segment is extended by the amount that the second rectangle
was reduced in the y-direction, and the x-directed line segment is extended by
the amount that the first rectangle was reduced in the x-direction. A determination
of whether the x-directed line segment and the y-directed line segment intersect
indicates if the first and second rectangles overlap.
