Calculate the length of a segment of a quadratic bezier
Asked Answered
P

3

9

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)

Pigment answered 7/8, 2012 at 22:16 Comment(0)
I
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)=\int_0^t\sqrt{At^2+Bt+C};dt

Which we can write as

eL(t)=\sqrt{A}\int_0^t\sqrt{t^2+2bt+c};dt

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

Then transforming u = t + b we get

L=\sqrt{A}\int_{b}^u\sqrt{u^2+k};dt)

Where k = c - b^2

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

L=\frac{\sqrt{A}}{2}\left(u\sqrt{u^2+k}-b\sqrt{b^2+k}+k\log\left|\frac{u+\sqrt{u^2+k}}{b+\sqrt{b^2+k}}\right|\right)

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 terms are computed more than once ...

Inefficiency answered 8/8, 2012 at 4:46 Comment(11)
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 readPigment
I mean because the link was taken down strangely and unexpectedly.. so now I am clueless. hahaPigment
Is there any chance you could remind me what A B and C are? in case the link stays down. :)Pigment
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_0Inefficiency
I think there might be an error? if b = B/A -> how come we get 2bt instead of one bt?Pigment
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. :)Pigment
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 itPigment
Yep taht was a typo, it should be b = B/(2A). Fixing that now.Inefficiency
I know it's a little bit old, but there is a typo in the final formula. It should be k * log(...)Barranquilla
@Barranquilla Agreed, I just double checked with Wolfram Alpha. Dont know how that got missed. Thanks.Inefficiency
@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 where is binary search based solution to find parameter for known arclength ...Maracaibo
I
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.

Inefficiency answered 8/8, 2012 at 4:6 Comment(2)
You don't need to use De-Casteljau's algorithm to create a new curve that spans from [0,t]. This post gives the closed-form equation for the new curve.Pull
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.Erastatus
J
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.

Jenine answered 17/3, 2016 at 15:13 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.