Pattern Matching Using Edge-Driven Dissected Rectangles

A method, executed by at least one processor of a computer, comprising:

• identifying matching rectangles in a layout design that match rectangle members of a search pattern based on edge operations and a first set of criteria, the rectangle members comprising an origin rectangle member and one or more reference rectangle members;
• attaching grid element identification values to the matching rectangles, the grid element identification values being associated with a regular grid that divides the layout design into a number of equal rectangle regions (grid elements);
• determining matching patterns in the layout design that match the search pattern based on a second set of criteria, the determining comprising analyzing the matching rectangles that match the one or more reference rectangle members in neighborhoods of the matching rectangles that match the origin rectangle member, wherein the neighborhoods are determined based on the grid element identification values;
• and
• storing the matching patterns.

A system comprising:

• one or more processors, the one or more processors programmed to perform a method, the method comprising:
• identifying matching rectangles in a layout design that match rectangle members of a search pattern based on edge operations and a first set of criteria, the rectangle members comprising an origin rectangle member and one or more reference rectangle members;
• attaching grid element identification values to the matching rectangles, the grid element identification values being associated with a regular grid that divides the layout design into a number of equal rectangle regions (grid elements);
• determining matching patterns in the layout design that match the search pattern based on a second set of criteria, the determining comprising analyzing the matching rectangles that match the one or more reference rectangle members in neighborhoods of the matching rectangles that match the origin rectangle member, wherein the neighborhoods are determined based on the grid element identification values;
• and
• storing the matching patterns.