US5113451A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for labelling polygons
Assignee: NXP BV
•
Filing: 1989-10-16
•
Granted: 1992-05-12
•
Expires: 2009-10-16
Abstract
Abstract A method for labelling polygons of a geometric layout which includes the steps of scanning a geometric layout during a first scan line pass to detect objects which form a polygon, processing the scan line at each occurrence of an event to detect the objects which contact the scan line, assigning temporary numbers and root designators to the objects which contact the scan line in accordance with a sorting criterion, updating the temporary numbers assigned to the objects to keep the temporary number associated with the earliest root designator of each separately detected polygon, and renaming each object which forms a part of the same polygon with a common label. The step of updating includes the steps of numbering each object in a polygon with a temporary number assigned to a root object of the polygon, and storing, in a sorted order, the root objects which lose their status as root objects during the step of updating.
Inventors
- 👤 David C. Chapman
- 👤 Herve G. Duprez
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 15:06
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398; G06V; G06V10/00; G06V10/40; G06V10/44; G06V10/457
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
157 words
A method for labelling polygons of a geometric layout which comprises the steps of: scanning the geometric layout during a first scan line pass to detect objects which form a polygon; processing the scan line at each occurrence of an event to detect the objects which contact the scan line; assigning temporary numbers and root designators to the objects which contact the scan line in accordance with a sorting criterion; updating the temporary numbers assigned to the objects to keep the temporary number associated with the earliest root designator of each separately detected polygon; and, renaming each object which forms a part of the same polygon with a common label, said step of updating including the steps of: numbering each object in a polygon with a temporary number previously assigned to the root object of the polygon; and, storing, in a sorted order, root objects which lose their status as root objects during the step of updating.
Claim 2
Independent Claim
157 words
A method for labelling polygons of a geometric layout which comprises the steps of: scanning the geometric layout during a first scan line pass to detect objects which form a polygon; processing the scan line at each occurrence of an event to detect the objects which contact the scan line; assigning temporary numbers and root designators to the objects which contact the scan line in accordance with a sorting criterion; updating the temporary numbers assigned to the objects to keep the temporary number associated with the earliest root designator of each separately detected polygon; and, renaming each object which forms a part of the same polygon with a common label, said step of updating including the steps of: numbering each object in a polygon with a temporary number previously assigned to the root object of the polygon; and, storing, in a sorted order, root objects which lose their status as root objects during the step of updating.
Claim 3
Dependent Claim
19 words
The method of claim 1, wherein said step of renaming further includes: scanning the geometric layout a second time.
Claim 4
Dependent Claim
24 words
The method of claim 1, wherein said step of updating further includes: identifying a single root object for each polygon of the geometric layout.
Claim 5
Dependent Claim
38 words
The method of claim 3 wherein said step of renaming further includes: scanning the geometric layout a second time; and, assigning to each object the common label which is correlated with the single root object for each polygon.
Claim 6
Dependent Claim
22 words
The method of claim 2, wherein the first scan line pass and the second scan line pass are in the same direction.
Claim 7
Dependent Claim
22 words
The method of claim 4, wherein the first scan line pass and the second scan line pass are in the same direction.
Claim 8
Dependent Claim
21 words
The method of claim 1, wherein said step of scanning includes: passing a horizontal scan line vertically across the geometric layout.
Claim 9
Dependent Claim
23 words
The method of claim 7, wherein said step of storing includes: sorting the objects in their order of appearance along the scan line.
Claim 10
Dependent Claim
26 words
The method of claim 1, wherein prior to said step of scanning, the polygons are broken into objects having parallel, horizontal upper and lower boundary lines.
Claim 11
Dependent Claim
20 words
The method of claim 1, wherein said objects detected during said step of scanning are nodes on the geometric layout.
Claim 12
Dependent Claim
31 words
The method of claim 1, wherein said step of renaming further includes the step of: processing the temporary numbers assigned to the objects together with the stored numbers of root objects.
Claim 13
Dependent Claim
24 words
The method of claim 1, wherein the processing of the scan line occurs upon the detection of the non-horizontal edges of a trapezoidal object.
Claim 14
Dependent Claim
32 words
The method of claim 1, wherein the root objects which lose their status as root objects are stored in a first temporary file with a canonical number of a winner root object.
Claim 15
Dependent Claim
22 words
The method of claim 13, wherein said step of processing is performed at a beginning and at an end of a polygon.
Claim 16
Dependent Claim
19 words
The method of claim 13, wherein said step of processing is performed at a point of contact between objects.
Claim 17
Dependent Claim
35 words
The method of claim 1, wherein said sorting criterion includes the steps of: sorting first by lower Y value, then by lower left X value of an object which forms a part of a polygon.
Claim 18
Dependent Claim
34 words
The method of claim 1, wherein said sorting criterion includes the steps of: sorting first by lower Y value, then by minimum left X value of an object which forms part of a polygon.
Claim 19
Dependent Claim
24 words
The method of claim 1, wherein the root objects which lose their status as root objects are stored in accordance with said sorting criterion.
Claim 20
Dependent Claim
54 words
The method of claim 1, wherein said step of renaming further includes the steps of: maintaining a reference count, for each root object, of the objects which have been assigned the temporary number of that root object; and, releasing an object as a root when the reference count for that root object becomes zero.
Claim 21
Dependent Claim
27 words
The method of claim 13, wherein said step of numbering further includes the step of: storing the temporary number of each object in a second temporary file.
Claim 22
Dependent Claim
38 words
The method of claim 20, wherein said step of renaming includes the steps of: assigning a final name to each object placed in the second temporary file on the basis of information stored in the first temporary file.
Claim 23
Independent Claim
133 words
A method for labelling polygons of a geometric layout which comprises the steps of: scanning a geometric layout during a first scan line pass to detect objects which form a polygon; processing the scan line at each occurrence of an event to detect the objects which contact the scan line; detecting an occurrence of a root object merge operation; assigning a label to each object which forms a part of the polygon during the first scan line pass; writing said label for each polygon to an output file as a final label during said assigning step until a root object merge operation is detected; initiating a second scan line pass when a root object merge is detected; and restarting said writing to said output file upon initiation of said second scan line pass.
Claim 24
Independent Claim
133 words
A method for labelling polygons of a geometric layout which comprises the steps of: scanning a geometric layout during a first scan line pass to detect objects which form a polygon; processing the scan line at each occurrence of an event to detect the objects which contact the scan line; detecting an occurrence of a root object merge operation; assigning a label to each object which forms a part of the polygon during the first scan line pass; writing said label for each polygon to an output file as a final label during said assigning step until a root object merge operation is detected; initiating a second scan line pass when a root object merge is detected; and restarting said writing to said output file upon initiation of said second scan line pass.
Claim 25
Dependent Claim
21 words
The method of claim 1, wherein said step of scanning includes: passing a vertical scan line horizontally across the geometric layout.
Claim 26
Dependent Claim
23 words
The method of claim 23, wherein said step of storing includes: sorting the objects in their order of appearance along the scan line.
Claim 27
Dependent Claim
26 words
The method of claim 1, wherein prior to said step of scanning, the polygons are broken into objects having parallel, vertical right and left boundary lines.
Claim 28
Dependent Claim
158 words
An integrated circuit fabricated using a process for labelling polygons which includes the steps of: scanning the geometric layout during a first scan line pass to detect objects which form a polygon; processing the scan line at each occurrence of an event to detect the objects which contact the scan line; assigning temporary numbers and root designators to the objects which contact the scan line in accordance with a sorting criterion; updating the temporary numbers assigned to the objects to keep the temporary number associated with the earliest root designator of each separately detected polygon; and, renaming each object which forms a part of the same polygon with a common label, said step of updating including the steps of: numbering each object in a polygon with a temporary number previously assigned to the root object of the polygon; and, storing, in a sorted order, root objects which lose their status as root objects during the step of updating.
Claim 29
Dependent Claim
158 words
An integrated circuit fabricated using a process for labelling polygons which includes the steps of: scanning the geometric layout during a first scan line pass to detect objects which form a polygon; processing the scan line at each occurrence of an event to detect the objects which contact the scan line; assigning temporary numbers and root designators to the objects which contact the scan line in accordance with a sorting criterion; updating the temporary numbers assigned to the objects to keep the temporary number associated with the earliest root designator of each separately detected polygon; and, renaming each object which forms a part of the same polygon with a common label, said step of updating including the steps of: numbering each object in a polygon with a temporary number previously assigned to the root object of the polygon; and, storing, in a sorted order, root objects which lose their status as root objects during the step of updating.
References Cited (Backward Citations)
US4183013A
Cited
US4189711A
Cited
US4630306A
Cited
US4624013A
Cited
US4718090A
Cited
US5018214A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-05-12 | 1995-11-11 | 1996-05-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-05-12 | 1999-11-11 | 2000-05-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-05-12 | 2003-11-11 | 2004-05-12 | $7700.00 | Window Closed / Lapsed |