Method of recognizing overlapped graphics in each degree of overlapping thereof
AssigneeDainippon Screen Mfg. Co., Ltd.
InventorMasayuki Tanimori
Life of this patent
Estimating the term…
Abstract
Segments forming respective graphics and relations of connection therebetween are recognized by vector type list structure. Sweep lines are provided at the apices and crosspoints of the graphics in order, and the segments are divided at the crosspoints. The divided segments are reconnected with each other while switching the connecting relation therebetween, whereby the graphics are reconstructed into those classified according to the degrees of overlapping thereof. A reconstructed graphic having a designated degree of overlapping is extracted and outputted.
Claims20
In a computer aided design system comprising a graphics data input means for inputting data representing figures of a circuit pattern of an integrated circuit, said figures having points in a coordinate system, a graphics processor for processing said input data and output means for displaying graphics obtained by said graphics processor, a method of recognizing an object graphic on which given first graphics overlap with each other at a designated degree of overlapping comprising the steps of:
- (a) making a first list of first segments defining given first graphics which are overlapped with each other on an image plane and storing said first list in a memory of said graphics processor;
- (b) recognizing respective apices and crosspoints of said first graphics through use of said first list;
- (c) dividing said first segments into partial segments at said crosspoints;
- (d) reconnecting said partial segments with each other at said crosspoint while changing a connecting relation among said partial segments so that reconnected partial segments form a boundary between areas on which said first graphics overlap with each other at different degrees of overlapping, respectively, to thereby convert said first graphics to second graphics which define an area on said image plane for each degree of overlapping of said first graphics;
- (e) storing said reconnected said partial segments in said memory;
- (f) making a second list of second segments defining respective contours of said second graphics and storing said second list in said memory;
- (g) selecting one segment within third segments which are included in said second segments and defining an area on which said first graphics overlap with each other at said designated degree of overlapping;
- (h) accessing said memory and extracting said third segments from said second list by tracing said third segments in said second list from said one segment, to recognize said object graphic defined by said third segments;
- and
- (i) transmitting said recognized object graphic to said output means.
In a computer aided design system comprising a graphics data input means for inputting data representing figures of a circuit pattern of an integrated circuit, said figures having points in a coordinate system, a graphics processor for processing said input data and output means for displaying graphics obtained by said graphics processor, a method of recognizing an object graphic on which given first graphics overlap with each other at a designated degree of overlapping comprising the steps of:
- (a) making a first list of first segments defining given first graphics which are overlapped with each other on an image plane and storing said first list in a memory of said graphics processor;
- (b) recognizing respective apices of said first graphics;
- (c) sorting said respective apices according to coordinates of said respective apices in a predetermined direction defined on said image plane, to define an order of said respective apices in said direction;
- (d) selecting a first apex from said respective apices according to said order;
- (e) specifying a part of said first segments which are located in a region following said first apex in said direction;
- (f) finding a crosspoint between said part of said first segments in said region through use of said first list;
- (g) dividing a part of said first segments which intercross at said crosspoint into partial segment;
- (h) reconnecting said partial segments with each other at said crosspoint while changing a connecting relation among said partial segments so that reconnected partial segments form a boundary between areas on which said first graphics overlap with each other at different degrees of overlapping, respectively;
- (i) storing said reconnected said partial segments in said memory;
- (j) repeating steps (d) through (i) while sequentially selecting said first apex according to said order, to thereby convert said first graphics to second graphics which define an area on said image plane for each degree of overlapping of said first graphics;
- (k) making a second list of second segments defining respective contours of said second graphics and storing said second list in said memory;
- (l) selecting one segment within third segments which are included in said second segments and defining an area on which said first graphics overlap with each other at said designated degree of overlapping;
- (m) accessing said memory and extracting said third segments from said second list by tracing said third segments in said second list from said one segment, to recognize said object graphic defined by said third segments;
- and
- (n) transmitting said recognized object graphic to said output means.
Dependencies are inferred from the claim text.