Patent US5500927A successfully refreshed from Google Patents.
US5500927A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for simplifying a computer-generated path
Assignee: Adobe Inc
•
Filing: 1993-03-18
•
Granted: 1996-03-19
•
Expires: 2013-03-18
Abstract
Abstract The present invention is for a system and process for simplifying complex graphical paths. The process first analyzes individual curve and straight line segments of the path, possibly splitting curved segments at local extrema points. Next, the process creates a list of points which includes the endpoints of all the original curve and straight line segments, as well as generating intermediate points along the curve and straight line segments. The process also flags each point in the list indicating what kind of point it is, or what the original path looks like at each point. Thereafter, the process flags any and all extrema points of the types the user specified. Then, the process uses a curve fitting routine for refitting each section of the path with new curves. The process tries to find a minimum set of curves which will reproduce the original path into a simplified version within the tolerances the user has specified.
Inventors
- 👤 Robert B. Sander-Cederlof
- 👤 John B. Ahlquist
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 07:23
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/23
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
231 words
A method implemented in a computer system of simplifying a graphical figure, said method comprising the steps of: inputting and storing a computer-generated graphical figure having a path into said computer system; receiving at least one tolerance value from an external source, said tolerance value determining an amount a more simplified path to be generated may deviate from said computer-generated path; parsing said computer-generated path to characterize information specific to said computer-generated path at points to be generated along said simplified path, the number of said points dependent upon said tolerance value, said method generating and storing a set of points for inputting to a curve-fitting routine for producing said simplified path, wherein said parsing step further comprises the steps of: analyzing individual line segments of said computer-generated path, wherein said line segments are comprised of straight and curved segments and said curved segments are divided at local extrema points; creating a list of points for each of said line segments; classifying each of said points based in part on said analyzation of said line segments; dividing into sections said list of points based upon said classifications of said points; inputting said sections of said list of points into said curve-fitting routine; and displaying on a display device coupled to said computer system a simplified graphical figure having a simplified path using said sections of points input into said curve-fitting routine.
Claim 2
Independent Claim
231 words
A method implemented in a computer system of simplifying a graphical figure, said method comprising the steps of: inputting and storing a computer-generated graphical figure having a path into said computer system; receiving at least one tolerance value from an external source, said tolerance value determining an amount a more simplified path to be generated may deviate from said computer-generated path; parsing said computer-generated path to characterize information specific to said computer-generated path at points to be generated along said simplified path, the number of said points dependent upon said tolerance value, said method generating and storing a set of points for inputting to a curve-fitting routine for producing said simplified path, wherein said parsing step further comprises the steps of: analyzing individual line segments of said computer-generated path, wherein said line segments are comprised of straight and curved segments and said curved segments are divided at local extrema points; creating a list of points for each of said line segments; classifying each of said points based in part on said analyzation of said line segments; dividing into sections said list of points based upon said classifications of said points; inputting said sections of said list of points into said curve-fitting routine; and displaying on a display device coupled to said computer system a simplified graphical figure having a simplified path using said sections of points input into said curve-fitting routine.
Claim 3
Dependent Claim
14 words
The method as recited in claim 1, wherein a user specifies said tolerance value.
Claim 4
Dependent Claim
38 words
The method as recited in claim 1, wherein said classifying step labels each of said points with an attribute selected from the group consisting of: a corner; an end-point; a local extrema; a smooth curve; and a tangent.
Claim 5
Dependent Claim
35 words
The method as recited in claim 1, wherein said analyzing step further comprises the steps of: determining an approximate average length of said straight segments; and determining an approximate average length of said curved segments.
Claim 6
Dependent Claim
17 words
The method as recited in claim 1, wherein said local extrema points may be horizontal or vertical.
Claim 7
Dependent Claim
25 words
The method as recited in claim 1, wherein said creating step further comprises the step of: placing end-points of said line segments into said list.
Claim 8
Dependent Claim
23 words
The method as recited in claim 1, wherein said creating step further comprises the step of: generating intermediate points within said line segments.
Claim 9
Dependent Claim
28 words
The method as recited in claim 1, wherein said classifying step further comprises the step of: specifying said local extrema points to be included in said simplified path.
Claim 10
Dependent Claim
21 words
The method as recited in claim 8 wherein said sections are bounded by either said corner or said local extrema points.
Claim 11
Dependent Claim
79 words
The method as recited in claim 9 wherein said classifying step further comprises the steps of: determining slopes of said path at each end of said sections; and fitting a single curve to each of said sections, said single curve having said determined slopes at each said end of said sections, said single curve passing through said ends, wherein a maximum distance between interior points along said path and said single curve is less than a predetermined tolerance value.
Claim 12
Dependent Claim
33 words
The method as recited in claim 10, further comprising the steps of: dividing said section at a point near said maximum distance; and fitting a single curve to each of said section divisions.
Claim 13
Dependent Claim
44 words
The method as recited in claim 11, further comprising the step of: replacing said single curve with a straight line segment when control points of a representation of said single curve are within a predetermined tolerance of said straight line segment connecting said ends.
Claim 14
Independent Claim
146 words
A method implemented in a computer system of simplifying a graphical figure, said method comprising the steps of: inputting and storing a computer-generated graphical figure having a path into said computer system; collecting information about a line segment within said path; creating a list of points that reside within said line segment, said list of points partially dependent upon said collected information; classifying each of said points in said list; examining said classified list of points for a local extrema; flagging any said local extrema found in said examining step; dividing said list of points into sections bounded by corner points and/or said local extrema; fitting either a straight line or a series of curves to each of said sections, resulting in a simplified line segment; and displaying on a display device coupled to said computer system a simplified graphical figure having said simplified line segment.
Claim 15
Independent Claim
146 words
A method implemented in a computer system of simplifying a graphical figure, said method comprising the steps of: inputting and storing a computer-generated graphical figure having a path into said computer system; collecting information about a line segment within said path; creating a list of points that reside within said line segment, said list of points partially dependent upon said collected information; classifying each of said points in said list; examining said classified list of points for a local extrema; flagging any said local extrema found in said examining step; dividing said list of points into sections bounded by corner points and/or said local extrema; fitting either a straight line or a series of curves to each of said sections, resulting in a simplified line segment; and displaying on a display device coupled to said computer system a simplified graphical figure having said simplified line segment.
Claim 16
Dependent Claim
25 words
The method as recited in claim 13 wherein said line segment is selected from the group consisting of: straight line segment; and curved line segment.
Claim 17
Dependent Claim
26 words
The method as recited in claim 14, further comprising the step of: dividing said curved line segment at said local extrema point after said collecting step.
Claim 18
Dependent Claim
22 words
The method as recited in claim 15 wherein said local extrema point is selected from the group consisting of: horizontal; and vertical.
Claim 19
Dependent Claim
43 words
The method as recited in claim 14 wherein said collecting step further comprises the steps of: determining an approximate average length of a plurality of said straight line segments; and determining an approximate average length of a plurality of said straight line segments.
Claim 20
Dependent Claim
31 words
The method as recited in claim 17 wherein said creating step further comprises the step of: placing a plurality of intermediate points of said line segment into said list of points.
Claim 21
Dependent Claim
39 words
The method as recited in claim 18 wherein an amount of said plurality of intermediate points is determined by a predetermined parameter modified by a ratio of an approximate length of said line segment and said approximate average length.
Claim 22
Dependent Claim
41 words
The method as recited in claim 13 wherein said creating step further comprises the steps of: placing end-points of said line segment into said list of points; and placing an intermediate point of said line segment into said list of points.
Claim 23
Dependent Claim
20 words
The method as recited in claim 20 wherein said placing of said intermediate point is dependent upon a predetermined parameter.
Claim 24
Dependent Claim
24 words
The method as recited in claim 13 wherein said classifying step adds information about said path through each of said points in said list.
Claim 25
Dependent Claim
32 words
The method as recited in claim 22 wherein said information indicates whether said path passing through a point in said list of points is a corner, a smooth curve, or a tangent.
Claim 26
Dependent Claim
23 words
The method as recited in claim 23 wherein said information further comprises data on whether a slope of said path is substantially vertical.
Claim 27
Dependent Claim
22 words
The method as recited in claim 23 wherein said information marks end-points as said corners when said path is an open path.
Claim 28
Dependent Claim
19 words
The method as recited in claim 13 wherein said simplified line segment approximates said path within a predetermined tolerance.
Claim 29
Dependent Claim
108 words
The method as recited in claim 13 wherein said fitting step further comprises the steps of: finding a first point in said list of points which is either a corner point or said extrema point; finding a next point in said list of points which is either said corner point or said extrema point, said first and next points defining a section of points; determining a slope of said path at each end of said section of points; and fitting, is able, a single curve to said section of points, said single curve having said slope at said each end, said single curve passing through said each end.
Claim 30
Dependent Claim
43 words
The method as recited in claim 27, further comprising the steps of: dividing said section of points when said fitting step is unable to fit said single curve to said section of points; and fitting individual curves to each of said divided sections.
Claim 31
Dependent Claim
29 words
The method as recited in claim 28 wherein said dividing step is continued in a recursive manner until said divided sections of points are reduced to two points each.
Claim 32
Dependent Claim
61 words
The method as recited in claim 28, further comprising the step of: replacing said simplified line segment with a straight line when said straight line would match said path within a predetermined tolerance, wherein said replacing step is performed when control points of a curve representation which defines said simplified line segment are within said predetermined tolerance of said straight line.
Claim 33
Dependent Claim
24 words
The method as recited in claim 29 wherein said slope at said local extrema is selected from the group consisting of: horizontal; and vertical.
Claim 34
Dependent Claim
33 words
The method as recited in claim 27 wherein said slope at a point that is not said local extrema is an average of slopes of nearest points on either side of said point.
Claim 35
Dependent Claim
37 words
The method as recited in claim 27 wherein said fitting step further comprises the step of: fitting a straight line to said section of points when said section contains only two points that are said corner points.
Claim 36
Dependent Claim
20 words
The method as recited in claim 13 wherein said path is comprised of more than one of said line segment.
References Cited (Backward Citations)
US4949281A
Cited
US5214754A
Cited
US5309521A
Cited
US5410645A
Cited
US5408598A
Cited
US5305432A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-03-19 | 1999-09-18 | 2000-03-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-03-19 | 2003-09-18 | 2004-03-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-03-19 | 2007-09-18 | 2008-03-19 | $7700.00 | Window Closed / Lapsed |