LineSegment-CubicBezier-Intersection Numerical Non-Deterministic Errors

Intersecting a Line with a CubicBezier does not reliably return correct results. Code to reproduce the error:

  const Geom::Point a{486, 597};
  const Geom::Point b{313, 285};
  const Geom::LineSegment line{std::vector<Geom::Point>{a, b}};

  const Geom::Point c{580.1377046525328, 325.5830744834947};
  const Geom::Point d{289.35338528516013, 450.62476639303753};

  {
    const Geom::CubicBezier curve{std::vector<Geom::Point>{c, c, d, d}};
    const auto cuts = curve.intersect(line);

    // FAIL! `cuts` is actually empty in this case, but I have observed cases where
    // `cuts` contained up to eight elements.
    // I expected it to contain exactly one element.
    EXPECT_EQ(cuts.size(), 1);
  }

  {
    const Geom::LineSegment curve{std::vector<Geom::Point>{c, d}};
    const auto cuts = curve.intersect(line);
    EXPECT_EQ(cuts.size(), 1);   // works.
  }

I found these values in an interactive application because the intersection visualization "flickered" when moving the endpoint of the line with the mouse. I.e., small deviations make a huge (apparently non-deterministic and erroneous) difference.

In the interactive application, the problem is much less severe (i.e., there's much less flickering, but it's still perceivable) if

• the control points of the CubicBezier curve are not collinear
• using CubicBezier-CubicBezier intersection rather than CubicBezier-LineSegment intersection (replaced the line (a, b) with a CubicBezier curve with control points (a, a, b, b))

The problem is symmetric, i.e., curve.intersect(line) is equivalent to line.intersect(curve).

I think that it's some numerical problem since when c is defined as

const Geom::Point c{580.1377046525328, std::nextafter(325.5830744834947, 0.0)};,

the test succeeds.