Robustness problems in path simplification

[raphlinus]

This is essentially a continuation of #264 but with concrete failing test cases. Thanks to @rachael-wang for providing the test code and data. I've put the code in a gist; the easiest way to run it is to place it in the examples/ directory.

Running this command on the attached test data produces the following SVG (blue is input, red is output):

cargo run --example simplify_svg 219561.txt > simplify_result.svg

As discussed in #264, the problem is partly that fit_to_bezpath_opt is being called with path data containing corners, and it is intended to be used for reasonably smooth input paths. One solution is to implement an additional layer to segment the input by corners and optimize each smooth subrange separately.

Another issue, though, is that this test case triggers robustness issues. For example, changing the accuracy parameter from 0.18 to 0.3 in the code trips a panic corresponding to no real roots of the quartic equation. At the minimum, this code should be changed to report a lack of solution so it can be recovered, rather than panicking.

219561.txt

[raphlinus]

In addition to the corner-handling robustness as mentioned above, there is another issue that deserves attention. In the looped Bézier segment toward the bottom of the figure, the error metric appears to be drastically underestimating the error between the source curve and approximation. I think I might know what's happening: in fit_to_cubic if a ray from the source curve fails to intersect the cubic at all, it returns an error larger than the provided accuracy parameter. In the fit_to_bezpath case that will always force a subdivision, but in the _opt variant it seems like there is at least one path where such a result is accepted without additional checking. That wouldn't happen if the error were monotonic in the subdivided range, but when the input curve is not smooth, that assumption is not valid.

[raphlinus]

Above analysis is not correct, it is not the case that fit_to_cubic returns cubics that exceed the accuracy parameter provided to it. Here's an alternate explanation.

The internal fit_opt_segment function attempts to find a parameter t1 so that the range t0..t1 can be fit with a single cubic with exactly the given accuracy, and uses the ITP method to do so. The ITP method, like bisection, maintains a bracket with a potential t1 value too small (error undershoots) and another too large. The normal case is that the error is a reasonably smooth function of the t1 parameter, in which case the arithmetic midpoint of the bracket is a reasonable value. However, in the presence of a corner, the error takes a huge jump when the corner is crossed. Thus, the error at the midpoint can be considerably higher than the tolerance. I think the solution to that is to tweak the ITP algorithm so that the t1 value on the low side of the bracket is always taken, as that guarantees that the resulting fit is within the error bound.