Finding a quadratic Bézier curve of length $l$ between two points

I have two points $P_1$ and $P_2$ in the plane. For each of the points, I have two vectors $v_1$ and $v_2$. I want to find a quadratic Bézier curve from $P_1$ to $P_2$ of length $l$ leaving $P_1$ in the direction of $v_1$ and entering $P_2$ in the direction of $v_2$.

Edit: It is not needed that I restrict myself to Bézier curves, it was just my first approach. Other ideas are more than welcome.

Also, as stated in the comments, this is not always possible, but I am only interested in the cases where it is possible.

-
Not possible in general. Your problem is overconstrained: $P_1$, $P_2$, $v_1$ and $v_2$ define a unique quadratic Bézier. –  Peter Taylor Mar 4 '11 at 13:29
It is obviously correct when you say that it is not possible in general. For example, the vectors could point away from each other, and $l$ could be the minimum distance between $P_1$ and $P_2$. But if I can solve the problem, in which way can I solve the problem? I do not need to restrict myself to Bézier curves. –  utdiscant Mar 4 '11 at 13:39
As long as $l > d(P_1, P_2)$ you should be able to find such a curve, by varying the length of your vectors $v_1$ and $v_2$. However, apparently (steve.hollasch.net/cgindex/curves/cbezarclen.html) there's no closed form for calculating the length of a cubic Bézier curve, so you'd have to use quadrature. –  Rawling Mar 4 '11 at 15:43

Let $Q$ be the intersection of the two end tangents defined by $(P_1, v_1)$ and $(P_2, v_2)$.

You can construct a rational quadratic Bezier curve (degree 2) with the required arclength $l$ provided $d(P_1,P_2) \le l < d(P_1,Q) + d(P_2,Q)$, where $d$ denotes the distance between two points. Rational quadratics are just conic section curves.

AFAIK, there is no closed-form solution that lets you construct the curve, for a given $l$, but a simple one-parameter root-finding process will give it to you reliably and quickly.

Unlike cubics, rational quadratics never have inflexions, which might be useful to you. And, for values of $l$ close to $d(P_1,Q) + d(P_2,Q)$, they give a solution that is arguably more "natural".

The basic formulae and some nice pictures can be found on this page.

-

cubic Bézier curves

The "curves" in most fonts and most other vector graphic formats -- PostScript, Asymptote, Metafont, SVG, etc. -- are Bézier splines composed of cubic Bézier curves.

A cubic Bézier curve is often represented as 4 points P0, P1, P2, P3. P0 is its starting point, P3 is its end point. By placing P1 anywhere along the ray from P0 in the direction of v1, the Bézier curve will leave P0 in the direction of v1. By placing P2 anywhere along the ray from P3 in the direction of -v2, the Bézier curve will enter P3 in the direction of v2.

If you place P1 directly on top of P0 and place P2 directly on top of P3, the "cubic Bézier curve" degenerates to a straight line from P0 to P3 with some minimum length. The further one pushes P1 away from P0 in the desired direction, or pushes P2 away from P3 in the desired direction, or (most likely) both, the arc length monotonically increases, and the curve still has the desired relationships. (If the two rays intersect, then when P1 and P2 are both pushed far enough past the intersection point, the cubic Bézier curve will have a self-intersection point ... somewhere).

The problem is still a little underconstrained -- you can increase the length by pushing P1, or increase it by pushing P2, or both.

If I had this problem, I would obtain some subroutine BezierArcLength(P0, P1, P2, P3) that gave me an adequate approximation of the actual length of some given cubic Bézier curve. Rawling suggested Earl Boebert: "Computing the Arc Length of Cubic Bezier Curves" which looks great; Arc Length of Bézier Curves has more discussion on this topic.

Then I would guess that maybe setting the distance m from P0 to P1 to be the same as the distance from P2 to P3 might be OK. So I would build some subroutine TestPoints(m) that sets P1 a distance m away from P0 along the desired ray, and sets P2 a distance m away from P3 along the desired ray.

Then I would use something like the false position method to find some m that gave me the desired length, with the function f(m) = BezierArcLength(TestPoints(m)) - desired_length.

Initialize by picking a=0, b=4*desired_length, and calculating fa = f(a) and fb = f(b). (TestPoints(0) gives a straight line shorter than your desired length, so fa is negative, and TestPoints(b) gives a curve longer than your desired length, so fb is positive, right?)

Loop:

• Find some new position m using the false position method: m = (fb*a - fa*b)/(fb - fa).
• Calculate the Bezier arc length excess over your desired length: fm = f(m).
• If fa and fm have the same sign, set the new a to m and set the new fa to fm.
• Otherwise, fb and fm have the same sign, so set the new b to m and set the new fb to fm.
• loop until fm is "close enough" to zero.

This converges on a cubic Bézier curve that meets your criteria. Other cubic Bézier curve that meets your criteria either push P1 directly towards P0 (making that distance less than m) and push P2 directly away from P3 (making that distance more than m), or vice versa.