Menu
I have a set of data points (which I can thin out) that I need to fit with a Bézier curve. I need speed over accuracy, but the fit should be decent enough to be recognizable. I'm also looking for an algorithm I can use that doesn't make much use of libraries (specifically NumPy).
I've read several research papers, but none has enough detail to fully implement. Are there any open-source examples?
312
Fitting the points to a Bezier curve will place them in the hull of the points. Using a spline will make sure your curve goes through all points. That said, creating the function that draws either is not complicated at all. Wikipedia has a nice article that will explain the basics, Bézier curve.
The most common way to fit curves to the data using linear regression is to include polynomial terms, such as squared or cubed predictors. Typically, you choose the model order by the number of bends you need in your line. Each increase in the exponent produces one more bend in the curved fitted line.
Despite its name, you can fit curves using linear regression. The most common method is to include polynomial terms in the linear model. Polynomial terms are independent variables that you raise to a power, such as squared or cubed terms.
Least-Squares Algorithm There are many proposed algorithms for curve fitting. The most well-known method is least squares, where we search for a curve such that the sum of squares of the residuals is minimum.
I have similar problem and I have found "An algorithm for automatically fitting digitized curves" from Graphics Gems (1990) about Bezier curve fitting. Additionally to that I have found source code for that article.
Unfortunately it is written in C which I don't know very well. Also, the algorithm is quite hard to understand (at least for me). I am trying to translate it into C# code. If I will be successful, I will try to share it.
File GGVecLib.c in the same folder as FitCurves.c contains basic vectors manipulation functions.
I have found a similar Stack Overflow question, Smoothing a hand-drawn curve. The approved answer provide C# code for a curve fitting algorithm from Graphic Gems.
154
What's missing in a lot of these answers is that you may not want to fit a single cubic Bézier curve to your data. More generally, you would like to fit a sequence of cubic Bézier curves, i.e., a piecewise cubic Bézier fit, to an arbitrary set of data.
There's a nice thesis dating from 1995, complete with MATLAB code, that does this:
% Lane, Edward J. Fitting Data Using Piecewise G1 Cubic Bezier Curves. % Thesis, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, 1995 http://www.dtic.mil/dtic/tr/fulltext/u2/a298091.pdf
To use this, you must, at minimum, specify the number of knot points, i.e., the number data points that will be used by the optimization routines to make this fit. Optionally, you can specify the knot points themselves, which increases the reliability of a fit. The thesis shows some pretty tough examples. Note that Lane's approach guarantees G1 continuity (directions of adjacent tangent vectors are identical) between the cubic Bézier segments, i.e., smooth joints. However, there can be discontinuities in curvature (changes in direction of second derivative).
I have reimplemented the code, updating it to modern MATLAB (R2015b). Contact me if you would like it.
Here's an example of using just three knot points (chosen automatically by the code) the fits two cubic Bézier segments to a Lissajous figure.
41
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
