getPoint(length) or getT(length) about bezierjs HOT 5 OPEN

Yeah a binary cut works, but a faster approach is to do the first few steps based on a one-time computed LUT for the curve. Computing length is expensive, so you generally want to cache any length computations you do for any specific t so you never have to do them again.

You can then do a preliminary binary search on the LUT to find the two t values between which the given distance can be found, and then do the real binary search iteration with distance computed for t using the two values as initial lower and upper bound. And as you can grow the LUT as you perform your binary search, the initial call can be based on a LUT [0:0, 1:1] (using distance represented as ratio to make the maths clearer), with LUT updates every time you do a length(t) call, just making the function take less time (at the cost of memory, but memory is cheap) the more you need to run it.

Extending the .length() function with a parameter t is relatively straight forward, it just requires changing the limits of integration. I've filed that separately as #34

from bezierjs.

good request, but note that this is actually really hard, since there is no universal way to symbolical reparameterize a Bezier curve for arc length.

from bezierjs.

Ive been playing with some illustrator script by hiroyuki sato , It looks like he uses an iterative approach , sub divide by half, is len great or smaller, then divide by half until 30 iterations or within a tolerance.

However it would be nice to use one library, how about...

• Implement a similar iterative approach
• change prototype.length() to include a t parameter length(t) which returns the length of the path from T=0 to T=X, this would allow me to implement my own approach.

His code is here, http://shspage.com/aijs/en .... in divide (length).jsx the actual code is below...

    // ------------------------------------------------
    // return the bezier curve parameter "t"
    // at the point which the length of the bezier curve segment
    // (from the point start drawing) is "len"
    // when "len" is 0, return the length of whole this segment.
    function getT4Len(q, len){
      var m = [q[3][0] - q[0][0] + 3 * (q[1][0] - q[2][0]),
               q[0][0] - 2 * q[1][0] + q[2][0],
               q[1][0] - q[0][0]];
      var n = [q[3][1] - q[0][1] + 3 * (q[1][1] - q[2][1]),
               q[0][1] - 2 * q[1][1] + q[2][1],
               q[1][1] - q[0][1]];
      var k = [ m[0] * m[0] + n[0] * n[0],
                4 * (m[0] * m[1] + n[0] * n[1]),
                2 * ((m[0] * m[2] + n[0] * n[2]) + 2 * (m[1] * m[1] + n[1] * n[1])),
                4 * (m[1] * m[2] + n[1] * n[2]),
                m[2] * m[2] + n[2] * n[2]];

       var fullLen = getLength(k, 1);

      if(len == 0){
        return fullLen;

      } else if(len < 0){
        len += fullLen;
        if(len < 0) return 0;

      } else if(len > fullLen){
        return 1;
      }

      var t, d;
      var t0 = 0;
      var t1 = 1;
      var torelance = 0.001;

      for(var h = 1; h < 30; h++){
        t = t0 + (t1 - t0) / 2;
        d = len - getLength(k, t);

        if(Math.abs(d) < torelance) break;
        else if(d < 0) t1 = t;
        else t0 = t;
      }

      return t;
    }

    // ------------------------------------------------
    // return the length of bezier curve segment
    // in range of parameter from 0 to "t"
    // "m" and "n" are coefficients.
    function getLength(k, t){
      var h = t / 128;
      var hh = h * 2;

      var fc = function(t, k){
        return Math.sqrt(t * (t * (t * (t * k[0] + k[1]) + k[2]) + k[3]) + k[4]) || 0 };

      var total = (fc(0, k) - fc(t, k)) / 2;

      for(var i = h; i < t; i += hh){
        total += 2 * fc(i, k) + fc(i + h, k);
      }

      return total * hh;
    }

from bezierjs.

Any chance that we are going to get this enhancement ?

from bezierjs.

Infinitely larger chance if someone wants to write the PR, I am terribly unavailable at the moment to do this work so it's on my todo list, but not very high on that list atm.

from bezierjs.