Use algebra to find intersections betwen line segments and quadratic/cubic Bézier curves

Rafał Siejakowskirequested to merge
S-Rafael/lib2geom:lin_x_bez into master

This MR changes the intersection method used in the case of a line segment being intersected with a quadratic or cubic Bézier curve.

Instead of running the iterative Bézier clipping algorithm, the intersection points are found algebraically in a single step. To this end, the Bézier curve is transformed to a coordinate system in which the line segment lies along the X-axis; the Y-component of the Bézier curve is then extracted as a polynomial; suitable roots of this polynomial give the intersections. Since the change affects degrees 2 and 3, these roots can be found algebraically.

The main advantages of this method are:

  • no accumulation of numerical errors, in contrast to iterative methods;
  • the number of returned intersections always makes sense (see #47 (closed));
  • potentially faster runtime.

The MR also adds extra tests for this specific scenario, including a regression test for the fixed issue.

Fixes #47 (closed)

Merge request reports