Method for determining whether two rectangles of an electronic circuit structure overlap

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.

BACKGROUND OF THE INVENTION

As a part of the normal integrated circuit (IC) design process, a consistency check of the physical layout of each layer of the IC, including metal layers, semiconductor layers, and the like, is normally performed on the IC design database to detect and correct any mistakes in the design. One of the checks typically performed on such a database is ensuring two adjacent rectangular portions of a layer, such as two metal connections of an IC metal layer, do not overlap. Such a condition often results in two separate circuits of the IC being inadvertently connected together, thus causing improper operation of the IC. Such database checks ordinarily must be performed many thousands of times for each IC due to the large number of transistors and other circuit components normally found in today's integrated circuit technologies. As a result, the amount of time required for each single operation of checking for overlap between two rectangles can significantly influence the overall time required to perform such a check on an entire IC design database.

Typically, checking for possible overlap of two rectangles is performed by iterating over the entire area of each of the rectangles in small sections to determine if any two such sections, one from each of the two rectangles, reside in the same area of the IC layer surface. Such iterations are necessarily time-consuming, causing an inordinate amount of computer processing time to be expended for that particular task.

Alternately, the boundaries of the two rectangles may be determined, and then each line segment defining the boundary of one rectangle may be compared against each line segment of the other rectangle in order to determine if any line segments of opposite rectangles intersect. Additionally, a check must be made to determine if one of the rectangles resides completely within the other, as no line segments of the two rectangles will intersect in that particular case, thereby reducing the usefulness of a simple line intersection check. Although this particular method is likely to be less computationally intensive than the iterative method, a significant amount of computing time is required nonetheless.

From the foregoing, a need exists for a faster method for detecting if two rectangular features of an electronic design structure, such as an IC metal or semiconductor layer, overlap. Such a method would significantly reduce the time required to check each pair of rectangles, thus reducing overall IC design time.

SUMMARY OF THE INVENTION

Embodiments of the invention, to be discussed in detail below, may be described as methods of modifying two rectangles of an electronic circuit structure 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 the 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. The problem of determining whether the rectangles overlap is then reduced to a determination of whether the single point representing the first rectangle resides within the enlarged rectangle representing the second original rectangle.

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 then extended by the amount that the second rectangle was reduced in the y-direction, while the x-directed line segment is extended by the amount that the first rectangle was reduced in the x-direction. Determination of whether the first and second rectangles overlap is then reduced to a determination of whether the x-directed line segment and the y-direct line segment intersect.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

One embodiment of the invention is shown conceptually in FIG.1throughFIG. 4, while a second embodiment is displayed in a similar fashion in FIG.6through FIG.9. In each of the figures, the sides of the rectangles are aligned parallel and perpendicular to an x-y coordinate system, as indicated by the x- and y-axes denoted in each of the figures.

Relating to the first embodiment, in FIG.1andFIG. 2a first rectangle1and a second rectangle2do not overlap. To determine whether the first rectangle1and the second rectangle2overlap, the first rectangle1is reduced along both the x-direction and y-direction, as shown inFIG. 1, from a rectangle to a single point3, as indicated in FIG.2. The single point3is positioned in the center of the first rectangle1. This positioning is accomplished by moving opposing sides of the rectangle equal distances toward each other along both the x-axis and the y-axis.

Similarly, the second rectangle2is expanded in both the x-direction and y-direction by moving opposing sides of the rectangle outward from the center of the second rectangle2. Each side of the second rectangle2is moved by a distance equal to that which the corresponding sides of the first rectangle1were moved in the opposite direction. For example, if each of the two vertical sides of the first rectangle1is moved toward the center of the first rectangle1along the x-axis by three distance units, each of the vertical sides of the second rectangle2are each moved away from the center of the second rectangle2by the same distance. The resulting enlarged rectangle4, as shown inFIG. 2, is centered about the second rectangle2of FIG.1. The arrows ofFIG. 1show the direction and magnitude of the movement for each side of the first rectangle1and the second rectangle2.

FIG. 2shows the result of the rectangle side movements indicated in FIG.1. The resulting configuration of the single point3and the enlarged rectangle4indicate whether the original first rectangle1and second rectangle2overlap. In the case ofFIG. 2, the single point3resides outside of the enlarged rectangle4, indicating that the first rectangle1and the second rectangle2do not overlap.

FIG.3andFIG. 4describe the situation in which the first rectangle1and the second rectangle2overlap. The same side movements for each of the rectangles is employed as described above for FIG.1and FIG.2. The resulting positions of the single point3and the enlarged rectangle4, as displayed inFIG. 4, indicate that the original first rectangle1and second rectangle2overlap in this case, since the single point3resides within the enlarged rectangle4.

These conceptual movements of sides of the rectangles are easily accomplished by way of a first computational method100, as shown inFIG. 5, which is essentially a simple algebraic procedure or algorithm representing these movements. First, the minimum and maximum x values (MIN x1and MAX x1), as well as the minimum and maximum y values (MIN y1and MAX y1), for the first rectangle1, and also the second rectangle2(MIN x2, MAX x2, MIN y2and MAX y2), are determined (step110). These values may be ascertained quickly, for example, by the x-y coordinate locations of opposing comers of each of the rectangles. Any other method for determining these values would also suffice.

The x-midpoint (xm1) and the y-midpoint (ym1) of the first rectangle1, thus defining the single point3described above, are then calculated (step130). Normally, the x-midpoint is ordinarily calculated by first subtracting the minimum x value of the first rectangle1from the maximum x value of the first rectangle1and then dividing by two to yield an x-difference value between the x-midpoint and one of the opposing vertical sides of the first rectangle1(xdiff1) (step120). The x-difference value is then added to the minimum x value of the first rectangle1to obtain the x-midpoint. Alternately, the x-difference may be subtracted from the maximum x value of the first rectangle1to yield the same result. The y-midpoint may be calculated in a corresponding manner. By way of algebraic formulae:
xdiff1=((MAXx1−MINx1)/2)
ydiff1=((MAXy1−MINy1)/2)
xm1=MINx1+xdiff1=MAXx1−xdiff1
ym1=MINy1+ydiff1=MAXy1−ydiff1

The x-difference and y-difference values (xdiff1and ydiff1) calculated above are also used to move the sides of the second rectangle2, resulting in the enlarged rectangle4(steps140through170). More specifically, Xdiff1is added to MAX x2and subtracted from MIN x2to define the minimum and maximum x values for the enlarged rectangle4(MIN xeand MAX xe). The minimum and maximum y values for the enlarged rectangle4(MIN yeand MAX ye) are calculated similarly:
MINxe=MINx2−xdiff1
MAXxe=MAXx2+xdiff1
MINye=MINy2−ydiff1
MAXye=MAXy2+ydiff1

Now that the rectangle conversions have been performed as described earlier, the x-midpoint and y-midpoint values, denoting the location of the single point3, are compared with the minimum and maximum x and y values of the enlarged rectangle4(step180). If the single point3resides within the minimum and maximum x and y values of the enlarged rectangle4, the first rectangle1and the second rectangle2overlap. In terms of a comparison formula:
If (MIN xe<xm1<MAX xe) and (MIN ye<ym1<MAX ye),then the first rectangle1and the second rectangle2overlap.

Cases where the single point3is located directly on the edge of the enlarged rectangle4, although not strictly representing an overlap condition, indicate that the first rectangle1and the second rectangle2are “touching,” thus possibly representing another undesirable configuration, depending on the particular application involved.

A second embodiment of the invention is described pictorially in FIG.6through FIG.9. With this embodiment, the first rectangle1is reduced in the x-direction, as shown in the non-overlapping rectangle case ofFIG. 6, resulting in a y-directed line segment5, passing through and centered upon the first rectangle1, as displayed in FIG.7. Conceptually, the vertical sides of the first rectangle1are each moved the same distance toward the center of the first rectangle1. Similarly, the second rectangle2is reduced in the y-direction, resulting in an x-directed line segment6which passes through and is centered upon the second rectangle2. Additionally, the length of the y-directed line segment5is the length of the first rectangle1along the y-axis, plus an additional length added to each end that is equal to the amount that each of the horizontal sides of the second rectangle2has been moved in the y-direction. Accordingly, the length of the x-directed segment6is the length of the second rectangle2along the x-axis, plus the amount that the first rectangle1was reduced in the x-direction. The arrows ofFIG. 6indicate the directions and magnitudes of the rectangle side movements described above.

FIG. 7shows the y-directed line segment5and the x-directed line segment6resulting from the graphical operations indicated in FIG.6. With this embodiment, the position of the two line segments5,6relative to each other determine if the original rectangles1,2overlap. More specifically, if the two line segments5,6intersect, the rectangles1,2overlap; otherwise, the rectangles1,2occupy separate spaces. In the specific case ofFIG. 7, the y-directed line segment5and the x-directed line segment6do not cross, indicating that the first rectangle1and the second rectangle2ofFIG. 6do not overlap.

The case of two overlapping rectangles is shown in FIG.8and FIG.9.FIG. 8displays the first rectangle1and the second rectangle2overlapping, with the same graphical operations performed on them as described in conjunction with FIG.6. These operations result in an y-directed line segment5and an x-directed line segment6that intersect, as shown inFIG. 9, thus indicating that the first rectangle1and the second rectangle2ofFIG. 8overlap.

Once again, these graphical operations may be performed efficiently using a series of concise algebraic operations, as shown in the second computational method200of FIG.10. Identical to the first computational method100described earlier, the minimum and maximum x and y values for both the first rectangle1(MIN x1, MAX x1, MIN y1, and MAX y1) and the second rectangle2(MIN x2, MAX x2, MIN y2, and MAX y2) are determined (step210). Ordinarily, these values are readily available by way of the x-y coordinates of the comers of the two rectangles1,2.

Next, the x-midpoint of the first rectangle1(xm1) and the y-midpoint of the second rectangle2(ym2) are calculated (step230). Normally, the x-midpoint of the first rectangle1is calculated by first subtracting the minimum x value of the first rectangle1from the maximum x value of the first rectangle1and then dividing by two to yield an x-difference value between the x-midpoint and one of the opposing vertical sides of the first rectangle1(xdiff1) (step220). The x-difference value may then be added to the minimum x value (or subtracted from the maximum x value) of the first rectangle1to obtain the x-midpoint for the first rectangle1. The y-midpoint for rectangle2may be calculated in a similar manner by first subtracting the minimum y value of the second rectangle2from the maximum y value of the second rectangle2and then dividing by two to yield a y-difference value between the y-midpoint and one of the opposing horizontal sides of the second rectangle2(ydiff2) (step220). The y-difference value is then added to the minimum y value (or subtracted from the maximum y value) of the second rectangle2to obtain the y-midpoint for the second rectangle2(step230). Mathematically speaking:

The x-difference and y-difference values (xdiff1and ydiff2) are also employed to move the corresponding sides of the first rectangle1and the second rectangle2away from their respective rectangle centers, resulting in the y-directed line segment5and the x-directed line segment6(steps240through270). In greater detail, xdiff1is added to MAX x2and subtracted from MIN x2to define the minimum and maximum x values for the x-directed line segment5(MIN x1sand MAX x1s). The minimum and maximum y values for the y-directed line segment (MIN y1sand MAX y1s) are calculated correspondingly using ydiff2:
MINx1s=MIN x2−xdiff1
MAXx1s=MAX x2+xdiff1
MINy1s=MIN y1−ydiff2
MAXy1s=MAX y1+ydiff2

Once again, now that the rectangle conversions have been performed as previously described, the MIN x1sand MAX x1svalues, denoting the location of the ends of the x-directed line segment6, are compared with the x-midpoint of the first rectangle1(xm1) (step280). Similarly, the MIN y1sand MAX y1svalues, denoting the location of the ends of the y-directed line segment5, are compared with the y-midpoint of the second rectangle2(ym2) (also step280). If the x-midpoint of the first rectangle1resides between the ends of the x-directed line segment6, and the y-midpoint of the second rectangle2resides between the ends of the y-directed line segment5, the first rectangle1and the second rectangle2overlap. Again, in mathematical terms:If (MIN x1s<xm1<MAX x1s) and (MIN y1s<ym2<MAX y1s),then the first rectangle1and the second rectangle2overlap.

Cases where the y-directed line segment5and the x-directed line segment6intersect at the very end of one of those lines5,6, while not strictly construed to be an overlap condition, indicate that the first rectangle1and the second rectangle2are “touching,” thus possibly representing another undesirable configuration of the rectangles1,2, depending on the particular situation to which embodiments of the invention are applied.

Aside from a straight-forward application of checking for overlap of two circuit structures, embodiments of the present invention may also be utilized to enforce IC design rules that require specified minimum distances between nearby rectangles of a circuit structure. In such a case, embodiments of the invention may be employed by expanding the actual circuit rectangles by an amount corresponding to the minimum inter-rectangle distance required by the design rules, and then checking to see if the expanded rectangles overlap.

Embodiments of the present invention may also be applied in other areas involving circuit design aside from integrated circuits. For example, printed circuit boards (PCBs) contain similar electronic circuit structures, comprising the one or more layers of those PCBs. Overlap of the rectangular elements, such as circuit traces, within these structures in the PCB design database often raises concerns analogous to those encountered with respect to IC design. As a result, use of embodiments of the invention may be employed within the PCB design environment to significant advantage.

From the foregoing, the invention provides streamlined methods for determining if two rectangles, as part of a larger electronic circuit structure, overlap. The methods can be performed using a modicum of memory storage and processing time compared to prior art methods. Embodiments of the invention other than those shown above are also possible. As a result, the invention is not to be limited to the specific forms so described and illustrated; the invention is limited only by the claims.