search

linebender / kurbo

A Rust library for manipulating curves
Apache License 2.0
727 stars 70 forks source link

Numerically approximate arc perimeter #381

Open tomcur opened 1 month ago

tomcur commented 1 month ago

This is on top of PR https://github.com/linebender/kurbo/pull/378.

This implementation uses Carlson symmetric forms (https://arxiv.org/abs/math/9409227v1) of incomplete elliptical integrals of the second kind to numerically approximate elliptical arc lengths. These forms have nice computational properties allowing quick convergence of the approximations (each iteration reduces the error bound by 4⁶). Boost and Gnu Scientific Library are some other projects using them.

The error bounds don't seem quite correct yet. In theory, and if my understanding is correct, the Carlson approximations should be bounded in relative error by the given relative error param (i.e., if the approximation converges to some value y, the true value is within y ± y*relative_error. I'll have to dig into it some more.

waywardmonkeys commented 1 month ago

I've no idea about the math here, but what Raph and I had discussed (somewhat) for #378 is that I would fix the one part that is broken and it could land and then a follow up (like this one?) would replace the current math with better math for the arclen operation.

tomcur commented 1 month ago

This is based on top of your PR, changing arclen only, so indeed requires your PR to be merged. I'll keep it rebased on top of your changes.

The arclen implementation here needs more work, but that can proceed independently from fixes in #378.

tomcur commented 1 month ago

Simplified a bit and hopefully all edge cases are now correct.

arclen's accuracy param is not handled yet, but the Carlson approximations can be iterated to arbitrary precision. The easiest is to guarantee a relative accuracy, but an absolute accuracy might also be possible with some careful calculations.

tomcur commented 1 month ago

I've optimized a bit, the implementation now requires three evaluations of the elliptic integrals, one of which is actually a complete integral and could be optimized with a quadratically converging approximation (which I suggest we leave for a later PR, that's also relevant for the Ellipse shape).