8

I use this algorithm to calculate the length of a quadratic bezier: http://www.malczak.linuxpl.com/blog/quadratic-bezier-curve-length/

However, what I wish to do is calculate the length of the bezier from 0 to t where 0 < t < 1

Is there any way to modify the formula used in the link above to get the length of the first segment of a bezier curve?

Just to clarify, I'm not looking for the distance between q(0) and q(t) but the length of the arc that goes between these points.

(I don't wish to use adaptive subdivision to aproximate the length)

Dan P
  • 135
  • 1
  • 7
AturSams
  • 7,568
  • 18
  • 64
  • 98

3 Answers3

10

Since I was sure a similar form solution would exist for that variable t case - I extended the solution given in the link.

Starting from the equation in the link:

L(t)

Which we can write as

L(t)

Where b = B/(2A) and c = C/A.

Then transforming u = t + b we get

L(t)

Where k = c - b^2

Now we can use the integral identity from the link to obtain:

L(t)

So, in summary, the required steps are:

  1. Calculate A,B,C as in the original equation.
  2. Calculate b = B/(2A) and c = C/A
  3. Calculate u = t + b and k = c -b^2
  4. Plug these values into the equation above.

[Edit by Spektre] I just managed to implement this in C++ so here the code (and working correctly matching naively obtained arc lengths):

float x0,x1,x2,y0,y1,y2;      // control points of Bezier curve
float get_l_analytic(float t) // get arclength from parameter t=<0,1>
    {
    float ax,ay,bx,by,A,B,C,b,c,u,k,L;
    ax=x0-x1-x1+x2;
    ay=y0-y1-y1+y2;
    bx=x1+x1-x0-x0;
    by=y1+y1-y0-y0;
    A=4.0*((ax*ax)+(ay*ay));
    B=4.0*((ax*bx)+(ay*by));
    C=     (bx*bx)+(by*by);
    b=B/(2.0*A);
    c=C/A;
    u=t+b;
    k=c-(b*b);
    L=0.5*sqrt(A)*
        (
         (u*sqrt((u*u)+k))
        -(b*sqrt((b*b)+k))
        +(k*log(fabs((u+sqrt((u*u)+k))/(b+sqrt((b*b)+k)))))
        );
    return L;
    }

There is still room for improvement as some therms are computed more than once ...

Spektre
  • 49,595
  • 11
  • 110
  • 380
Michael Anderson
  • 70,661
  • 7
  • 134
  • 187
  • oops, I just realized I have no idea how to do this cause A, B and C are not numbers, they are 2-tuples.. :) But it was interesting to read – AturSams Aug 11 '12 at 10:53
  • I mean because the link was taken down strangely and unexpectedly.. so now I am clueless. haha – AturSams Aug 11 '12 at 10:54
  • Is there any chance you could remind me what A B and C are? in case the link stays down. :) – AturSams Aug 11 '12 at 11:07
  • 2
    From google cache: `A=4(a_x^2+a_y^2)` `B=4(a_x b_x + a_y b_y)` `C=b_x^2+b_y^2` where `a = P_0 - 2 P_1 + P_2` and `b = 2P_1 - 2 P_0` – Michael Anderson Aug 11 '12 at 22:16
  • I think there might be an error? if b = B/A -> how come we get 2bt instead of one bt? – AturSams Aug 12 '12 at 15:39
  • but it's cool, this helped me a lot and I managed to find an answer for the integral of sqrt(a * x^2 + b * x + c) and use it to solve this using the integral you mentioned in the first line and plugging in the values for the variables. :) – AturSams Aug 12 '12 at 15:41
  • There might be an error somewhere in there but I think this provides more than enough information to get an idea of how to solve it – AturSams Aug 12 '12 at 16:41
  • 1
    Yep taht was a typo, it should be `b = B/(2A)`. Fixing that now. – Michael Anderson Aug 14 '12 at 00:55
  • I know it's a little bit old, but there is a typo in the final formula. It should be k * log(...) – holtaf May 26 '16 at 11:35
  • @holtaf Agreed, I just double checked with Wolfram Alpha. Dont know how that got missed. Thanks. – Michael Anderson May 27 '16 at 01:13
  • @MichaelAnderson thanks for this +1 it helped a lot... I added working C++ code for this I needed for this related QA: [Optimize quadratic curve tracing using numeric methods](https://stackoverflow.com/a/74637798/2521214) where is binary search based solution to find parameter for known arclength ... – Spektre Dec 02 '22 at 08:14
2

While there may be a closed form expression, this is what I'd do:

Use De-Casteljau's algorithm to split the bezier into the 0 to t part and use the algorithm from the link to calculate its length.

Michael Anderson
  • 70,661
  • 7
  • 134
  • 187
  • You don't need to use De-Casteljau's algorithm to create a new curve that spans from [0,t]. [This post](http://stackoverflow.com/a/11705483/238419) gives the closed-form equation for the new curve. – BlueRaja - Danny Pflughoeft Jun 02 '15 at 01:17
  • Specifically, quadratic curves have an arc length integral with a less-than-quintic polynomial portion, so we can symbolically solve that. Anything higher than quadratic (cubic, quartic, etc) can't be solved symbolically and require numerical analysis instead. – Mike 'Pomax' Kamermans Dec 01 '22 at 23:55
2

You just have to evaluate the integral not between 0 and 1 but between 0 and t. You can use the symbolic toolbox of your choice to do that if you're not into the math. For instance:

http://integrals.wolfram.com/index.jsp?expr=Sqrt\[a*x*x%2Bb*x%2Bc\]&random=false

Evaluate the result for x = t and x = 0 and subtract them.

Peter O.
  • 32,158
  • 14
  • 82
  • 96
user1225999
  • 912
  • 8
  • 14