[Lib2geom-devel] Curve fitting (was Including BSD-Licenced code in Inkscape)

[Tavmjong B. <tav...@fr...>]

Hi Alexander,

Looks interesting.

As you are proposing this as an addition to lib2geom, the proper place
to discuss this is on the lib2geom-devel list (lib2geom is a semi-
independent project):

    lib...@li...

Tav

 
> 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
> 
> -------------------------------------------------------------------
> -----------
> _______________________________________________
> Inkscape-devel mailing list
> Ink...@li...
> https://lists.sourceforge.net/lists/listinfo/inkscape-devel