Patent ID: 7908579

Claim:
A computer-implemented method of performing an electronic design automation operation upon polygons in an integrated circuit design, comprising: receiving an integrated circuit design, the integrated circuit design comprising a plurality of polygons; clustering, by using a processor, the plurality of polygons to form clusters, in which the act of clustering is performed by: determining vertices of the plurality of polygons as corresponding vertices of a plurality of trapezoids; sorting the corresponding vertices of the plurality of trapezoids; storing the corresponding vertices of the plurality of trapezoids in a file; and constructing the clusters based at least in part upon the corresponding vertices of the plurality of trapezoids, wherein at least one of the clusters is represented as a tree structure such that a node of the tree structure corresponds to at least one of the plurality of trapezoids; identifying a pattern of polygons that is shared among the clusters having the same pattern of polygons; performing the electronic design automation operation upon the pattern of polygons to generate an operation result; replicating the operation result on the clusters having the same pattern of polygons without performing the electronic design automation operation upon the clusters; and storing the operation result in a volatile or non-volatile computer readable medium or display the operation result on a display device.