26
\$\begingroup\$

See also: same question on Math.SE

How can I find the arclength of a Bezier curve? For example, a linear Bezier curve has the length:

length = sqrt(pow(x[1] - x[0], 2) + pow(y[1] - y[0], 2));

But what about quadratic, cubic, or n-degree Bezier curves?

(My goal was to estimate a sampling resolution beforehand, so I don't have to waste time checking if the next point is touching the previous point.)

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You should reword the question to refer to the length of the curve, that is a much more straightforward (and searchable) term. \$\endgroup\$
    – Sparr
    Nov 28, 2010 at 11:34
  • \$\begingroup\$ i suggest posting this on math, i'm sure some clever face over there will give you the answer in one of them clever web fonts :p \$\endgroup\$
    – Tor Valamo
    Nov 28, 2010 at 17:27
  • 2
    \$\begingroup\$ @Tor I did (yesterday), but I've been told it's very complicated, and hence unpractical. [ math.stackexchange.com/q/12186/2736 ] \$\endgroup\$ Nov 28, 2010 at 21:08
  • \$\begingroup\$ Supposedly clothoid curves/splines are an alternative to beziers, and have closed-form arclength expressions, but I don't know much about this yet. (Trying to generate equal-distance points along a curve.) Catenaries also have closed-form arc length expressions? \$\endgroup\$
    – endolith
    Feb 21, 2014 at 16:43

4 Answers 4

11
\$\begingroup\$

A simple way for cubic Beziers is to split the curve into N segments and sum the segments' lengths.

However, as soon as you need the length of only part of the curve (e.g. up to a point 30% of the length along), arc-length parameterization will come into play. I posted a fairly long answer on one of my own questions about Béziers, with simple sample code.

\$\endgroup\$
1
  • \$\begingroup\$ I'm doing this for the LEGO Mindstorms NXT, which has a really weak processor (48Mhz), so I need as much speed as possible. I'll take the dividing approach to conserve some speed, and get it accurate enough (for "non-realtime" rendering). I also have a option in which you can set the value of 1.0/t (called resolution), so that's for "realtime" (which is at best 10fps on the slow NXT). Every iteration, t += resolution, and a new point/line is drawn. Anyways, thanks for the idea. \$\endgroup\$ Nov 29, 2010 at 0:58
8
\$\begingroup\$

Arc lengths for Bezier curves are only closed form for linear and quadratic ones. For cubics, it is not guaranteed to have a closed solution. The reason is arc length is defined by a radical integral, for which has a closed for only 2nd degree polynomials.

Just for reference: The length of a quadratic Bezier for the points (a,p) (b,q) and (c,r) is

$$ \frac{(a^2(q^2 - 2qr + r^2) + 2a(r - q)(b(p - r) + c(q - p)) + (b(p- r) + c(q - p))^2)\ln{\frac{\sqrt{a^2 - 2ab + b^2 + p^2 - 2pq + q^2} \sqrt{a^2 + 2a(c - 2b) + 4b^2 - 4bc + c^2 + (p - 2q + r)^2} + a^2 + a(c - 3b) + 2b^2 - bc + (p - q)(p - 2q + r) }{\sqrt{a^2 + 2a(c - 2b) + 4b^2 - 4bc + c^2 + (p - 2q + r)^2} \sqrt{b^2 - 2bc + c^2 + q^2 - 2qr + r^2} + a(b - c) - 2b^2 + 3bc - c^2 + (p - 2q + r)(q - r)}}}{a^2 + 2a(c - 2b) + 4b^2 - 4bc + c^2 + (p - 2q + r)^2}^\frac{3}{2} + \frac{\sqrt{(a^2 - 2ab + b^2 + p^2 - 2pq + q^2) (a^2 + a(c - 3b) + 2b^2 - bc + (p - q)(p - 2q + r)) - \sqrt{b^2 - 2bc + c^2 + q^2 - 2qr + r^2} (a(b - c) - 2b^2 + 3bc - c^2 + (p - 2q + r)(q - r))}}{a^2 + 2a(c - 2b) + 4b^2 - 4bc + c^2 + (p - 2q + r)^2} $$

Hence, it should be easier and cheaper approximate the arc by some other rule, like a polygon or an integration scheme like Simpson's rule, because square roots the LN are expensive operations.

\$\endgroup\$
1
  • 6
    \$\begingroup\$ This looks like something you'd draw on a blackboard in a movie to show how much of a genius someone is. \$\endgroup\$
    – Bemmu
    Aug 11, 2020 at 16:17
4
\$\begingroup\$

While I am d'accord with the answers you got already, I want to add a simple but powerful approximation mechanism which you can use for any degree Bézier curves: You continually subdivide the curve using de Casteljau subdivision until the maximum distance of the control points of a sub-curve to the sub-curve's baseline is below some constant epsilon. In that case the sub-curve can be approximated by its baseline.

In fact, I believe this is the approach usually taken when a graphics subsystem has to draw a Bézier curve. But do not quote me on this, I do not have references at hand at the moment.

In practice it will look like this: (except the language is irrelevant)

public static Line[] toLineStrip(BezierCurve bezierCurve, double epsilon) {
    ArrayList<Line> lines = new ArrayList<Line>();

    Stack<BezierCurve> parts = new Stack<BezierCurve>();
    parts.push(bezierCurve);

    while (!parts.isEmpty()) {
        BezierCurve curve = parts.pop();
        if (distanceToBaseline(curve) < epsilon) {
            lines.add(new Line(curve.get(0), curve.get(1)));
        } else {
            parts.addAll(curve.split(0.5));
        }
    }

    return lines.toArray(new Line[0]);
}
\$\endgroup\$
2
  • \$\begingroup\$ While this is a good approach, I've heard of numerical instability at high-order Bezier curves, which require another idea: splitting the the higher-order curves into smaller cubic curves. \$\endgroup\$ Sep 21, 2015 at 0:31
  • \$\begingroup\$ Also, if the end goal is an accurate estimate, it might be a good idea to approximate with quadratics instead of lines to ensure that we don't understate our estimate at locations of high curvature. \$\endgroup\$ Sep 21, 2015 at 0:33
2
\$\begingroup\$

I worked out the closed form expression of length for a 3 point Bezier (below). I've not attempted to work out a closed form for 4+ points. This would most likely be difficult or complicated to represent and handle. However, a numerical approximation technique such as a Runge-Kutta integration algorithm would work quite well by integrating using the arc length formula. My Q&A on RK45 on MSE may help with RK45 implementation.

Here is some Java code for the arc length of a 3 point Bezier, with points a,b, and c.

    v.x = 2*(b.x - a.x);
    v.y = 2*(b.y - a.y);
    w.x = c.x - 2*b.x + a.x;
    w.y = c.y - 2*b.y + a.y;

    uu = 4*(w.x*w.x + w.y*w.y);

    if(uu < 0.00001)
    {
        return (float) Math.sqrt((c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y));
    }

    vv = 4*(v.x*w.x + v.y*w.y);
    ww = v.x*v.x + v.y*v.y;

    t1 = (float) (2*Math.sqrt(uu*(uu + vv + ww)));
    t2 = 2*uu+vv;
    t3 = vv*vv - 4*uu*ww;
    t4 = (float) (2*Math.sqrt(uu*ww));

    return (float) ((t1*t2 - t3*Math.log(t2+t1) -(vv*t4 - t3*Math.log(vv+t4))) / (8*Math.pow(uu, 1.5)));
\$\endgroup\$
1
  • \$\begingroup\$ Given the number of transcendental functions it is presumably much faster to calculate it using a non-closed form. \$\endgroup\$
    – Timmmm
    Mar 28, 2020 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .