Hi,
I added a curve fitting algorithm to 2geom which takes a std::vector of Geom::Point and fits a Geom::CubicBezier to the points.
It fits (non-degenerate) cubic bezier curves to given points within half a millisecond up to an error of 1e-9.
You can find it here: https://github.com/abrock/lib2geom
In src/test/bezier-fit-test.cpp I made three simple tests, one "normal" curve and two (nearly) degenerate curves with (nearly) colinear points. I create a Cubic Bezier, select 20 points and give these to the fitting function (which doesn't know the original curve).
Results:
Normal Curve: Speed: 2678 curves per second Worst error: 1.31799e-10 at t=0.736842
Degenerate Curve: New method: 1567.89 curves per second Worst error: 6.84045e-09 at t=0.110945
Nearly degenerate curve: New method: 534.738 curves per second Worst error: 0.0284499 at t=0.0958247
in src/2geom/bezier-utils.cpp are the new functions:
- fit_bezier sets up the nonlinear least squares problem
Helper functions: - bezierfit_f calculates residuals - bezierfit_df calculates derivatives of residuals - bezier_distance helps calculating derivatives, it mainly contains a templated evaluation of Cubic Bezier functions.
src/2geom/jet.h contains the implementation of dual numbers I copied from the Ceres source code
Best Regards, Alexander