How long is that Bézier?

Re:How long is that Bézier? by foxes on Saturday December 29, 2018 @10:12PM (#18787123)

  Integrate[Sqrt[a + b u + c u^2 + d u^3], u]

Produces a huge expression which is a sum of EllipticF[ArcSin[#]] terms. I think it would be better to try and numerically compute the integral.

[ Parent | on HN ]

Re:How long is that Bézier? by xyzzyz on Saturday December 29, 2018 @11:21PM (#18787359)

No, that’s precisely my point: this expression can be evaluated faster and more accurately than by applying generic numeric integration method. Computing this EllipticF function is not different than computing natural logarithm, and if you don’t mind latter, there is not much reason to shy from former.

[ Parent | on HN ]

Re:How long is that Bézier? by foxes on Sunday December 30, 2018 @12:34AM (#18787615)

To be specific

r1,r2,r3 are roots of a+bu+cu^2+u^3,

Cleaning up the output a bit, you get

(2 (b c EllipticF[ArcSin[Sqrt[(-u+r3)/(-r2+r3)]],(r2-r3)/(r1-r3)] (u-r2) (u-r3) Sqrt[(-u+r1)/(r1-r3)]-9 a d EllipticF[ArcSin[Sqrt[(-u+r3)/(-r2+r3)]],(r2-r3)/(r1-r3)] (u-r2) (u-r3) Sqrt[(-u+r1)/(r1-r3)]+(c+3 d u) (a+u (b+u (c+d u))) Sqrt[((-u+r2) (u-r3))/(r2-r3)^2] (r2-r3)+2 c^2 (u-r2) (u-r3) Sqrt[(-u+r1)/(r1-r3)] (EllipticF[ArcSin[Sqrt[(-u+r3)/(-r2+r3)]],(r2-r3)/(r1-r3)] r1+EllipticE[ArcSin[Sqrt[(-u+r3)/(-r2+r3)]],(r2-r3)/(r1-r3)] (-r1+r3))-6 b d (u-r2) (u-r3) Sqrt[(-u+r1)/(r1-r3)] (EllipticF[ArcSin[Sqrt[(-u+r3)/(-r2+r3)]],(r2-r3)/(r1-r3)] r1+EllipticE[ArcSin[Sqrt[(-u+r3)/(-r2+r3)]],(r2-r3)/(r1-r3)] (-r1+r3))))/(15 d Sqrt[a+u (b+u (c+d u))] Sqrt[-(((u-r2) (u-r3))/(r2-r3)^2)] (r2-r3)).

But I guess if EllipticF is fast to compute, finding the roots can also be done pretty quickly, so yes its probably not that bad.

[ Parent | on HN ]

Re:How long is that Bézier? by raphlinus on Sunday December 30, 2018 @01:22AM (#18787775)

You need to integrate the square root of a quartic polynomial – the derivative of a cubic is a quadratic, then you square the norm of that, which gives a quartic. I spent a little time in Mathematica and it there is a solution, but it seems very unlikely to me it's going to be more efficient than numerical integration - it involves finding the roots of a quartic and has nine elliptic function evaluations. From a slide I found[0] it looks like it takes on the order of 100ns to compute an elliptic function, so at best it's still going to be slower than the adaptive quadrature even with an accuracy of 1e-12 or so. Plus there are a lot of divisions by differences of roots, and as each one of those approaches zero there will be numerical stability issues.

Long story short, it looks doable, but is a lot of work to get right and has almost no chance of beating out numerical integration in performance.

[0] http://arith22.gforge.inria.fr/slides/05-fukushima.pdf

[ Parent | on HN ]