US5566288A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for automatically fitting a B-spline curve to a set of data points
Assignee: Caterpillar Inc
•
Filing: 1994-09-02
•
Granted: 1996-10-15
•
Expires: 2014-09-02
Abstract
Abstract A B-spline curve is automatically generated as an approximating curve to a set of data points. A set of four control points are selected at equal intervals along a path defined by a set of data points. A B-spline curve is generated using these control points and the resultant B-spline curve is compared to the path to determine the separation between the B-spline curve and the path. If the separation exceeds a threshold separation, then additional one or more control points are added and the curve generated. The process of adding one or more control points continues until the curve approximates the path along the data points within a specified level of separation. A control point is then removed from the solution and the curve is then regenerated and again compared to the path. If there is no adverse effect resulting from the removal of this control point, the control point is left out of the solution. If, however, removal of the control point adversely impacted the fit of the B-spline curve to the data points, that control point is returned to the solution. This process of checking a control point to determine whether it can be removed from the solution is repeated for the remainder of the control points.
Inventors
- 👤 Craig Koerhsen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 16:13
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/17
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
93 words
A method for generating a curve to approximate a set of data points, comprising the steps of: (A) selecting a plurality of control points, wherein said control points are selected independently of characteristics of a path formed by the set of data points; (B) generating the curve based on said control points; (C) comparing the curve to the data points; and (D) if the curve is separated from at least one of the data points by more than a threshold amount, then (1) selecting an additional control point, and (2) repeating steps (B)-(D).
Claim 2
Independent Claim
93 words
A method for generating a curve to approximate a set of data points, comprising the steps of: (A) selecting a plurality of control points, wherein said control points are selected independently of characteristics of a path formed by the set of data points; (B) generating the curve based on said control points; (C) comparing the curve to the data points; and (D) if the curve is separated from at least one of the data points by more than a threshold amount, then (1) selecting an additional control point, and (2) repeating steps (B)-(D).
Claim 3
Dependent Claim
63 words
The method according to claim 1, further comprising the steps of: (E) removing at least one of said control points; (F) generating the curve based on said remaining control points; and (G) comparing the curve to the data points; (H) if the curve is separated from one of the data points by more than said threshold amount, then replacing said removed control point.
Claim 4
Dependent Claim
21 words
The method according to claim 2, further comprising the step of repeating said steps (E)-(H) for each of said control points.
Claim 5
Dependent Claim
31 words
The method according to claim 2, wherein said step (E) comprises the step of removing said plurality of control points selected in said step (A) that are not end data points.
Claim 6
Dependent Claim
37 words
The method according to claim 1, wherein said step of selecting an additional control point comprises the step of selecting all of the data points that are separated from the curve by more than said threshold amount.
Claim 7
Dependent Claim
31 words
The method according to claim 1, wherein said step of selecting an additional control point comprises the step of selecting the data point at which separation from the curve is greatest.
Claim 8
Dependent Claim
35 words
The method according to claim 1, wherein said step of selecting an additional control point comprises the step of selecting a data point in an area where separation from the curve exceeds said threshold amount.
Claim 9
Dependent Claim
28 words
The method according to claim 7, wherein said data point selected is the data point that is separated from the curve by the greatest distance in said area.
Claim 10
Dependent Claim
24 words
The method according to claim 7, wherein said data point selected is the data point that is approximately in the middle of said area.
Claim 11
Dependent Claim
42 words
The method according to claim 1, wherein said step of selecting an additional control point comprises the step of selecting a control point approximately midway between two existing control points for an area of the curve where the separation exceeds the threshold.
Claim 12
Dependent Claim
26 words
The method according to claim 10, wherein said additional control point is coincident with a data point that is approximately midway between two existing control points.
Claim 13
Dependent Claim
18 words
The method according to claim 10, wherein said additional control point is not coincident with a data point.
Claim 14
Dependent Claim
18 words
The method according to claim 1, wherein each of said control points are coincident with a data point.
Claim 15
Dependent Claim
35 words
The method according to claim 1, wherein said step of selecting an additional control point, comprises the step of selecting at least one control point in all areas where said separation exceeds said threshold amount.
Claim 16
Dependent Claim
37 words
The method according to claim 1, wherein said step of selecting an additional control point, comprises the step of selecting at least one control point in at least one area where said separation exceeds said threshold amount.
Claim 17
Dependent Claim
33 words
The method according to claim 1, wherein the step of selecting a plurality of control points comprises the step of selecting control points of approximately equal spacing along the set of data points.
Claim 18
Independent Claim
145 words
A method for generating a curve to approximate a set of data points, comprising the steps of: (A) selecting a plurality of control points, wherein said control points are selected independently of characteristics of a path formed by the set of data points; (B) generating the curve based on said control points; (C) comparing the curve to the data points; and (D) if the curve is separated from at least one of the data points by more than a threshold amount, then (1) selecting an additional control point, and (2) repeating steps (B)-(D); (E) removing at least one of said control points; (F) generating the curve based on said remaining control points; (G) comparing the curve to the data points; and (H) if the curve is separated from one of the data points by more than said threshold amount, then replacing said removed control point.
Claim 19
Independent Claim
145 words
A method for generating a curve to approximate a set of data points, comprising the steps of: (A) selecting a plurality of control points, wherein said control points are selected independently of characteristics of a path formed by the set of data points; (B) generating the curve based on said control points; (C) comparing the curve to the data points; and (D) if the curve is separated from at least one of the data points by more than a threshold amount, then (1) selecting an additional control point, and (2) repeating steps (B)-(D); (E) removing at least one of said control points; (F) generating the curve based on said remaining control points; (G) comparing the curve to the data points; and (H) if the curve is separated from one of the data points by more than said threshold amount, then replacing said removed control point.
Claim 20
Dependent Claim
37 words
The method according to claim 17, wherein said step of selecting an additional control point comprises the step of selecting all of the data points that are separated from the curve by more than said threshold amount.
Claim 21
Dependent Claim
28 words
The method according to claim 18, wherein said data point selected is the data point that is separated from the curve by the greatest distance in said area.
Claim 22
Dependent Claim
26 words
The method according to claim 19, wherein said additional control point is coincident with a data point that is approximately midway between two existing control points.
Claim 23
Dependent Claim
18 words
The method according to claim 19, wherein said additional control point is not coincident with a data point.
Claim 24
Dependent Claim
24 words
The method according to claim 18, wherein said data point selected is the data point that is approximately in the middle of said area.
Claim 25
Dependent Claim
31 words
The method according to claim 17, wherein said step of selecting an additional control point comprises the step of selecting the data point at which separation from the curve is greatest.
Claim 26
Dependent Claim
35 words
The method according to claim 17, wherein said step of selecting an additional control point comprises the step of selecting a data point in an area where separation from the curve exceeds said threshold amount.
Claim 27
Dependent Claim
42 words
The method according to claim 17, wherein said step of selecting an additional control point comprises the step of selecting a control point approximately midway between two existing control points for an area of the curve where the separation exceeds the threshold.
Claim 28
Dependent Claim
18 words
The method according to claim 17, wherein each of said control points are coincident with a data point.
Claim 29
Dependent Claim
35 words
The method according to claim 17, wherein said step of selecting an additional control point, comprises the step of selecting at least one control point in all areas where said separation exceeds said threshold amount.
Claim 30
Dependent Claim
37 words
The method according to claim 17, wherein said step of selecting an additional control point, comprises the step of selecting at least one control point in at least one area where said separation exceeds said threshold amount.
Claim 31
Dependent Claim
33 words
The method according to claim 17, wherein the step of selecting a plurality of control points comprises the step of selecting control points of approximately equal spacing along the set of data points.
References Cited (Backward Citations)
US5471573A
Cited
US5500927A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-10-15 | 2000-04-15 | 2000-10-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-10-15 | 2004-04-15 | 2004-10-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-10-15 | 2008-04-15 | 2008-10-15 | $7700.00 | Window Closed / Lapsed |