Cubic Bezier-based piecewise curve fitting method
Technical Field
The invention relates to the technical field of computer graphic curve fitting, in particular to a cubic Bezier-based piecewise curve fitting method.
Background
Bezier curves are the basic tools for computer graphics image modeling, and are one of the most used basic lines for graphics modeling. Bezier curves are also often used in industrial design to design the subject of a product, for example in aerospace navigation-related terrain software, which generally has the function of providing simulated flight: a user inputs a plurality of control points, a flight route is formulated, and then the flight is carried out along the simulation route; in some industrial product designs, a user is often required to input outer contour points of some industrial products, then contour lines are fitted according to the contour points, and finally product processing is performed according to the contour lines through a machine tool. In short, this requires that we fit an optimal curve (closed or non-closed) from the given control points.
The traditional curve fitting method has a high-order polynomial interpolation method, and a certain function is approximated by a polynomial to calculate a corresponding function value. Generally, the more the degree of the polynomial is, the more data is needed, and the more accurate the prediction is, but as the interpolation degree is higher, the longer the interpolation result deviates from the original function, the longer the ronge phenomenon occurs. In addition, a piecewise curve method is proposed, but continuity at a connecting point of the piecewise curve is only ensured, and the overall curve has no smoothness. Some people propose a construction algorithm for control points of a segmented continuous cubic Bezier curve, but the curve fitted by the method passes through all the control points, the algorithm is complex, the calculated amount is large, the smooth effect is not achieved, and when the distance between adjacent control points is very close, the curve fitted by the method often has wrong results such as deformation and the like.
Disclosure of Invention
The invention aims to provide a cubic Bezier-based piecewise curve fitting method to solve the technical problems of high complexity, low efficiency and incapability of fitting closed or non-closed curves simultaneously in the conventional curve fitting method.
The technical scheme adopted by the invention is as follows:
the invention provides a cubic Bezier-based piecewise curve fitting method, which comprises the following steps of:
s1, inputting original point p1,p2,…,pn;
S2, selecting a plurality of points q from the original points1,q2,…,qmThe other original points are used as the middle connection points of each piecewise curve;
s3, if the number of the intermediate connection points between the two adjacent end points is less than two, supplementing a virtual original point between the two end points by an interpolation method to be used as the intermediate connection point, otherwise, continuing to execute the step S4;
s4, taking the head end point of each piecewise curve as a head end control point, taking the tail end point as a tail end control point, constructing a linear equation set taking the middle control point of the piecewise curve as a solving target according to the middle connection point of each piecewise curve, and solving two middle control points of each piecewise curve between the head end control point and the tail end control point, wherein the method specifically comprises the following steps:
s41, obtaining a cubic Bezier formula as shown in formula (1):
wherein t is a parameter and is obtained by dividing the distance between the intermediate connecting point and the head point of the piecewise curve by the total length of all the original points in the piecewise curve after being sequentially connected; piControl points for piecewise curves, P0And PnRespectively coinciding with the head end point and the tail end point of the sectional curve; b isi,3(t) is a Bernstein basis function, as shown in equation (2):
constructing a cubic Bezier curve in each piecewise curve, then:
making two adjacent Bezier curves in each piecewise curve symmetric with respect to their intermediate connection point, there are:
then the target equation is obtained:
s42, solving the target equation by using a least square method to obtain a linear equation set:
s43, if fitting the non-closed curve, k is 1, …, m-1, and equation (9) is used to find two intermediate control points between the head end control point and the tail end control point of each piecewise curve; if a closed curve is fitted, k is 1, …, m-2, and two intermediate control points of each piecewise curve between the head end control point and the tail end control point are obtained by using a formula (10);
and S5, fitting a Bezier curve according to all the head end control points, the tail end control points and the middle control points.
The technical effect of the technical scheme is as follows: a smooth curve is fitted by adopting a piecewise continuous cubic Bezier curve, so that the curve has second-order continuity at the piecewise connection point, and the fitted curve avoids the generation of the Runge phenomenon; the method can avoid solving known quantities such as a head end control point and a tail end control point of each piecewise curve, thereby reducing the complexity of the algorithm and improving the execution efficiency of the algorithm, thereby meeting the requirements of actual industrial production; the method can fit closed and non-closed curves at the same time, has high algorithm flexibility and can meet the requirements of various practical conditions.
Alternatively, in step S1, the endpoints are sequentially arranged at equal intervals.
In order to make the aforementioned objects, features and advantages of the present invention comprehensible, embodiments accompanied with figures are described in detail below.
Drawings
In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the drawings needed to be used in the embodiments will be briefly described below, it should be understood that the following drawings only illustrate some embodiments of the present invention and therefore should not be considered as limiting the scope, and for those skilled in the art, other related drawings can be obtained according to the drawings without inventive efforts.
FIG. 1 is a flow chart of a cubic Bezier-based piecewise curve fitting method according to an embodiment of the present invention;
FIG. 2 is a graph showing the fitting result of a closed curve according to an embodiment of the present invention, where FIG. 2(a) is the input original points, and FIG. 2(b) is the result of fitting the original points by the method;
FIG. 3 is a graph showing the fitting result of another closed curve in the embodiment of the present invention, in which FIG. 3(a) is the input original points, and FIG. 3(b) is the result obtained by fitting the original points by the method;
fig. 4 is a diagram showing the fitting result of a non-closed curve in the embodiment of the present invention, in which fig. 4(a) is an input original point, and fig. 4(b) is a result obtained by fitting the original point by the present method.
Detailed Description
In order to make the objects, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are some, but not all, embodiments of the present invention. The components of embodiments of the present invention generally described and illustrated in the figures herein may be arranged and designed in a wide variety of different configurations.
Thus, the following detailed description of the embodiments of the present invention, presented in the figures, is not intended to limit the scope of the invention, as claimed, but is merely representative of selected embodiments of the invention. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.
Examples
Referring to fig. 1, the present embodiment provides a cubic Bezier-based piecewise curve fitting method, including the following steps:
s1, inputting original point p1,p2,…,pn;
S2, selecting a plurality of points q from the original points1,q2,…,qmSelecting the end points as the end points of each sectional curve, wherein the end points are distributed at equal intervals as much as possible, and other original points are used as middle connecting points of each sectional curve;
s3, if the number of the intermediate connection points between the two adjacent end points is less than two, supplementing a virtual original point between the two end points by an interpolation method to be used as the intermediate connection point, otherwise, continuing to execute the step S4;
s4, taking the head end point of each piecewise curve as a head end control point, taking the tail end point as a tail end control point, constructing a linear equation set taking the middle control point of the piecewise curve as a solving target according to the middle connection point of each piecewise curve, and solving two middle control points of each piecewise curve between the head end control point and the tail end control point, wherein the method specifically comprises the following steps:
s41, obtaining a cubic Bezier formula as shown in formula (1):
wherein t is a parameter and is obtained by dividing the distance between the intermediate connecting point and the head point of the piecewise curve by the total length of all the original points in the piecewise curve after being sequentially connected; piControl points for piecewise curves, P0And PnRespectively coinciding with the head end point and the tail end point of the sectional curve; b isi,3(t) is a Bernstein basis function, as shown in equation (2):
constructing a cubic Bezier curve in each piecewise curve, then:
making two adjacent Bezier curves in each piecewise curve symmetric with respect to their intermediate connection point, there are:
then the target equation is obtained:
s42, solving the target equation by using a least square method to obtain a linear equation set:
where i, j are both traversal symbols.
S43, if fitting the non-closed curve, k is 1, …, m-1, and equation (9) is used to find two intermediate control points between the head end control point and the tail end control point of each piecewise curve; if a closed curve is fitted, k is 1, …, m-2, and two intermediate control points of each piecewise curve between the head end control point and the tail end control point are obtained by using a formula (10);
and S5, fitting a Bezier curve according to all the head end control points, the tail end control points and the middle control points.
In this embodiment, the basic idea is to fit a smooth curve with piecewise continuous cubic Bezier curves, such that the curve has second order continuity at the piecewise connecting points. In order to obtain the optimal curve, i.e. the minimum error between the fitted curve and the original points, a system of linear equations is constructed using the least squares method, the intermediate control points of each piecewise curve are obtained by solving the system of equations, and finally a cubic Bezier curve is constructed in each segment using the initially selected end points and the solved intermediate control points, to complete curve fitting, as shown in figures 2, 3 and 4 which are examples of curves fitted using the method described in this embodiment, wherein, fig. 2 is the fitting of a closed curve (the left image is the input original point, the right image is the result obtained by fitting the original point by the method), fig. 3 is also the fitting of the closed curve (the left image is the input original point, the right image is the result obtained by fitting the original point by the method), and fig. 4 is the fitting of a non-closed curve (the left image is the input original point, and the right image is the result obtained by fitting the original point by the method).
The above description is only a preferred embodiment of the present invention and is not intended to limit the present invention, and various modifications and changes may be made by those skilled in the art. Any modification, equivalent replacement, or improvement made within the spirit and principle of the present invention should be included in the protection scope of the present invention.