Spline from `fit_from_points` has discontinuity

[nicolaschan]

There are sometimes discontinuities in the bezier spline given from Curve::fit_from_points. I expect the spline to consist of connecting curves. Since the spline does connect most of the time, I think it must be a bug when it isn't connected.

I've attached an example with points that trigger this bug with flo_curves = "0.7.2".

mod test {
    use flo_curves::{bezier, BezierCurve, BezierCurveFactory, Coord2};

    #[test]
    fn test_demonstrate_discontinuity() {
        let points = vec![
            Coord2(72.0, 216.0),
            Coord2(73.0, 217.0),
            Coord2(74.0, 218.0),
            Coord2(75.0, 219.0),
            Coord2(74.0, 220.0),
            Coord2(75.0, 221.0),
            Coord2(75.0, 222.0),
            Coord2(75.0, 223.0),
            Coord2(76.0, 224.0),
            Coord2(77.0, 225.0),
            Coord2(77.0, 226.0),
            Coord2(77.0, 227.0),
            Coord2(78.0, 227.0),
            Coord2(79.0, 227.0),
            Coord2(80.0, 228.0),
            Coord2(79.0, 229.0),
            Coord2(80.0, 230.0),
            Coord2(81.0, 231.0),
            Coord2(82.0, 232.0),
            Coord2(82.0, 233.0),
            Coord2(82.0, 234.0),
            Coord2(83.0, 235.0),
            Coord2(83.0, 236.0),
            Coord2(83.0, 237.0),
            Coord2(84.0, 238.0),
            Coord2(85.0, 239.0),
            Coord2(84.0, 240.0),
            Coord2(83.0, 241.0),
            Coord2(82.0, 241.0),
            Coord2(81.0, 241.0),
            Coord2(80.0, 242.0),
            Coord2(80.0, 243.0),
            Coord2(80.0, 244.0),
            Coord2(81.0, 245.0),
            Coord2(80.0, 246.0),
            Coord2(81.0, 247.0),
            Coord2(82.0, 248.0),
            Coord2(83.0, 249.0),
            Coord2(84.0, 250.0),
            Coord2(84.0, 251.0),
            Coord2(84.0, 252.0),
            Coord2(83.0, 251.0),
            Coord2(82.0, 251.0),
            Coord2(81.0, 251.0),
            Coord2(80.0, 250.0),
            Coord2(81.0, 249.0),
            Coord2(80.0, 248.0),
            Coord2(79.0, 247.0),
            Coord2(78.0, 246.0),
            Coord2(78.0, 245.0),
            Coord2(78.0, 244.0),
            Coord2(77.0, 243.0),
            Coord2(76.0, 242.0),
            Coord2(76.0, 241.0),
            Coord2(76.0, 240.0),
            Coord2(75.0, 239.0),
            Coord2(75.0, 238.0),
            Coord2(75.0, 237.0),
            Coord2(74.0, 237.0),
            Coord2(73.0, 237.0),
            Coord2(72.0, 236.0),
            Coord2(73.0, 235.0),
            Coord2(72.0, 234.0),
            Coord2(71.0, 233.0),
            Coord2(71.0, 232.0),
            Coord2(71.0, 231.0),
            Coord2(70.0, 230.0),
            Coord2(69.0, 229.0),
            Coord2(68.0, 228.0),
            Coord2(67.0, 227.0),
            Coord2(66.0, 226.0),
            Coord2(65.0, 225.0),
            Coord2(65.0, 224.0),
            Coord2(65.0, 223.0),
            Coord2(64.0, 223.0),
            Coord2(63.0, 223.0),
            Coord2(64.0, 222.0),
            Coord2(65.0, 222.0),
            Coord2(66.0, 222.0),
            Coord2(65.0, 221.0),
            Coord2(66.0, 220.0),
            Coord2(66.0, 219.0),
            Coord2(66.0, 218.0),
            Coord2(65.0, 217.0),
            Coord2(65.0, 216.0),
            Coord2(65.0, 215.0),
            Coord2(64.0, 214.0),
            Coord2(64.0, 213.0),
            Coord2(64.0, 212.0),
            Coord2(64.0, 211.0),
            Coord2(64.0, 210.0),
            Coord2(63.0, 209.0),
            Coord2(62.0, 208.0),
            Coord2(62.0, 207.0),
            Coord2(62.0, 206.0),
            Coord2(61.0, 205.0),
            Coord2(62.0, 204.0),
            Coord2(61.0, 204.0),
            Coord2(60.0, 204.0),
            Coord2(60.0, 203.0),
            Coord2(60.0, 202.0),
            Coord2(59.0, 201.0),
        ];
        let spline = bezier::Curve::fit_from_points(&points, 1.0).unwrap();
        let mut last = None;
        for curve in spline {
            if let Some(last) = last {
                if curve.start_point() != last {
                    panic!(
                        "Discontinuity detected between ({:?}, {:?}) and ({:?}, {:?})",
                        last.0,
                        last.1,
                        curve.start_point().0,
                        curve.start_point().1
                    );
                }
            }
            last = Some(curve.end_point());
        }
    }
}

The output is:

---- example::test::test_demonstrate_discontinuity stdout ----
thread 'example::test::test_demonstrate_discontinuity' panicked at src/example.rs:115:21:
Discontinuity detected between (60.0, 203.0) and (60.0, 202.0)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

[Logicalshift]

The algorithm can detect corners, so it's not unexpected that sometimes it will produce two curves where the tangent at the end of one does not match the following curve. In this case, you've specified a maximum error for the fit of 1.0, but only provided coordinates that align on integer boundaries, so there are some corners - there probably aren't a sequence of 'smooth' curves that can match these points to that level of accuracy. That looks like this:

You can decrease the accuracy of the fit to match the accuracy of your samples. For example, with a maximum error of 3.0, you'll get this:

Another approach would be to filter the input to reduce the noise and then use a higher level of fit. For instance, applying a gaussian filter to the input of the fitting function and a maximum error of 0.5 would create a result like this:

Averaging together neighboring points would also smooth out the results a bit, but a gaussian filter provides considerably more control over the result. I've put the code I used to generate these examples here: https://github.com/Logicalshift/flo_curves/blob/v0.8/demos/curve_fit/src/main.rs

The fitting function isn't really doing anything incorrect in the first case, though: it's meant to detect sudden changes in direction and interpret them as corners, and with a small error your data set has a lot of changes in direction.

[nicolaschan]

Thanks for the explanation! I really like the Gaussian filter idea.

On my end I've been filling the discontinuity by connecting them with a line, but that might not make sense for the library to do internally. As you said, it indicates that my points need some preprocessing anyway.

P.S. Thanks for the library. It's the best bezier curve fitter I've found.