Patent US4815009A successfully refreshed from Google Patents.
US4815009A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Algorithm for filling an image outline
Assignee: Xerox Corp
•
Filing: 1987-04-21
•
Granted: 1989-03-21
•
Expires: 2007-04-21
Abstract
Abstract A method of converting an outine defined by a plurality of vectors into an optimum set of trapezoids which can be filled in using standard printer techniques. The process is to determine all points in the outline where two vectors intersect, and the location of all scan lines that intersect these points. Then a winding number is calculated for each trapezoid formed by the scan lines and vectors, and Fill or Not Fill states are assigned to all trapezoids. Finally, all adjacent Fill areas separated by vectors are joined to form a final set of trapezoids which define the area to be filled.
Inventors
- 👤 Vladimir Blatin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 04:49
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/40
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
126 words
A method of displaying a filled in outline on a raster output scanner by partitioning said outline into trapezoids having parallel sides in the fast scan direction of said raster output scanner, said outline defined as one or more trajectories, each trajectory comprising a plurality of connected vectors, comprising the steps of: first determining the location of all intersecting points between vectors, second determining the location of all parallel scan lines passing through said intersecting points, calculating a winding number for each area bounded by said vectors and lines, and combining all adjacent areas separated only by vectors, but not by parallel lines, and having winding numbers in the fill state, to produce a final set of trapezoids, and filling in said final set of trapezoids.
Claim 2
Independent Claim
126 words
A method of displaying a filled in outline on a raster output scanner by partitioning said outline into trapezoids having parallel sides in the fast scan direction of said raster output scanner, said outline defined as one or more trajectories, each trajectory comprising a plurality of connected vectors, comprising the steps of: first determining the location of all intersecting points between vectors, second determining the location of all parallel scan lines passing through said intersecting points, calculating a winding number for each area bounded by said vectors and lines, and combining all adjacent areas separated only by vectors, but not by parallel lines, and having winding numbers in the fill state, to produce a final set of trapezoids, and filling in said final set of trapezoids.
Claim 3
Dependent Claim
78 words
The method of claim 1 wherein the winding number for a first area is calculated as one more or less than the winding number of a second area that is separated from said first area by a single vector, the direction of said single vector between said areas determining whether the winding number of the second area is one more or less than the first, and wherein the area outside the outline is assigned a number of 0.
Claim 4
Dependent Claim
16 words
The method of claim 1 wherein numbers in the fill state are defined as odd numbers.
Claim 5
Dependent Claim
16 words
The method of claim 1 wherein numbers in the fill state are defined as non-zero numbers.
Claim 6
Independent Claim
109 words
A method of filling in an outline generated as one or more trajectories, each trajectory comprising a plurality of vectors, said outline to be printed on a raster output scanner, comprising the steps of: determining the location of all points where said vectors intersect, identifying all scan lines intersecting said points, said scan lines and said vectors dividing said outline into areas bounded on two sides by scan lines and on two sides by vectors, calculating a winding number for each area, combining into one trapezoid all adjacent areas that have winding numbers in the "Fill" state and which are separated only by vectors, and filling in all trapezoids.
Claim 7
Independent Claim
109 words
A method of filling in an outline generated as one or more trajectories, each trajectory comprising a plurality of vectors, said outline to be printed on a raster output scanner, comprising the steps of: determining the location of all points where said vectors intersect, identifying all scan lines intersecting said points, said scan lines and said vectors dividing said outline into areas bounded on two sides by scan lines and on two sides by vectors, calculating a winding number for each area, combining into one trapezoid all adjacent areas that have winding numbers in the "Fill" state and which are separated only by vectors, and filling in all trapezoids.
Claim 8
Dependent Claim
64 words
The method of claim 5 wherein said winding number for a first area is calculated as one more or less than the winding number of a second area that is separated from said first area by a single vector, the direction of said vector between said areas determining whether the winding number of the second area is one more or less than the first.
Claim 9
Dependent Claim
16 words
The method of claim 5 wherein numbers in the fill state are defined as odd numbers.
Claim 10
Dependent Claim
16 words
The method of claim 5 wherein numbers in the fill state are defined as non-zero numbers.
References Cited (Backward Citations)
US4331955A
Cited
US4603431A
Cited
US4718105A
Cited
US4730261A
Cited
US4631532A
Cited
US4635050A
Cited
US4658247A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-03-20 | 1992-09-19 | 1993-03-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-03-20 | 1996-09-19 | 1997-03-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-03-20 | 2000-09-19 | 2001-03-21 | $7700.00 | Window Closed / Lapsed |