extend length() to accept a limit of integration about bezierjs HOT 4 OPEN

Hi Pomax,

You have some neat stuff here!

One question though, is it really necessary to sum over all the weights up to n=24?

I wrote an implementation a while back that you can see here (line 114) - with reference to Guenter, Parent "Motion Control: Computing the Arc Length of Parametric Curves". Sadly the reference is no longer openly available, but a copy can be requested here.

My own comments indicate that LGQ is exact for polynomials of order <= 2n-1, i.e. for cubics 2n-1=3 such that n=2, so the first two weights should give an exact result for cubics. I may have misread or not understood the problem, but my above example seems to give a good result. Though, without being certain, it may just be a fair approximation.

from bezierjs.

Also, binary subdivision comes from Guenter and Parent - it works pretty well too. :)

from bezierjs.

That depends entirely on your needs, really. For accuracy, n=24 is a good trade-off against speed, but you can get "visually acceptable" lenghts for low values like n=6. (For the true answer, we would have to integrate with an infinite number of weights applied to an infinite number of abscissae so that's clearly not happening).

The claim that LGQ is exact for 2n-1 sounds intriguing, but also highly unlikely; before trying to prove this using maths, let's see if I can falsify this claim with some examples:

If I try a curve (0,0)--(0,400)--(400,400)--(400,0) in your code, which has true length 800, then your code claims an approximate length of 799.998 - the true length is 800, so your approximation is ever so slightly off, whereas the bezierjs code using n=24 reports 800 clean, but that could just be an IEEE rounding artifact, which might just need reordering the mathematical operations to get rid of, but isn't enough to say the claim has been falsified. However, the fact that we can get the right answer using LGQ with n=24, however, suggests we at least want to try another case to see if we get a similar difference, or whether this is not attributable to mere rounding.

So, to test this further, let's pick a curve that is virtually guaranteed to mess things up for any almost-but-not-quite algorithm: if I change the curve to the cusped form (0,0)--(400,400)--(0,400)--(400,0), which has a length 732.193 (up to three decimal places), then we see that your code claims an approximate length length 731.367. That value is rather off by a lot ("almost an entire unit value!") if we needed a precise value, but is off by virtually nothing if we merely care about getting it right for visual purposes ("not even 1/732nd!").

Given these results, it seems the idea that LGQ can be exact does not hold at least for the cubic case, determined without having to resort to lots of time spent on writing out the (in)equalities and the error thresholds associated with LGQ. But, we also see that low values of n can yield perfectly usable results depending on your need for precision: they just won't be usable by everyone, may not be reliable for things like constant speed curve traversal, and cannot be relied upon for things like length alignment.

As for binary subdivision: that works well, but we're using computers and so we need to make sure we minimize errors introduced by IEEE floating point numbers (which are the worst) unless we have access to arbitrary precision decimals, or a fast symbolic resolver. Binary subdivision is fast, but inaccurate, whereas LGQ is a bit slower, but has arbitrary precision so as application designer you get more freedom in how fast you want things to run vs. how much precision your users will need (with the freedom to tweak that trade-off on every call, because not even length request needs to be super precise).

from bezierjs.

Very good points. I was mostly concerned with speed over accuracy and I suppose I latched onto the idea. The original paper might be worth looking into more as it seems that was where I saw mention of exactness.

from bezierjs.