Just ask Raph Levien.

hhp

You can ask the question on math forum: http://math.stackexchange.com/. Basically you have to solve the equation "absolute distance(P1, P1.4) = constant" and express P1.4 point with Bezier equation with one variable t.
In case of unusual bezier segments there may be more (maybe even up to 4?) resulting points with equal distance to the P1.

From what I understand there should be a possibility to invert the combination of these two funtions so one could hand over the absolute distance and receive the positions of the P1,4.

The set of all points of distance K from point P1 is a circle of radius K. If you compute the intersection of that circle with bezier P1234, that's your point.

The cubic Bezier can be written as a vector-valued function (x(t),y(t)) parameterized by the single variable t for 0<=t<=1. You want to find the value of t such that the distance from (x(t),y(t)) to P1 is a fixed value. Thus, (as Miha said) you wish to solve the equation sqrt((x(t)-P1.x)^2+(y(t)-P1.y)^2)=constant (*). Moving the constant to the left side, you want to find when the function f(t)=sqrt((x(t)-P1.x)^2+(y(t)-P1.y)^2)-constant is equal to 0 for 0<=t<=1. This can be efficiently solved using Newton's Method; this will be significantly faster than the binary search approach you described above since it uses information from the derivative. Newton's Method is iterative but converges quickly, so you can quickly compute the answer to the level of precision that you need.

One trick to simplify applying Newton's Method is to square both sides of equation (*) first. This will give the same t value, but then the function f(t) becomes a polynomial in t. This is easier to differentiate. The resulting polynomial has degree 6, and so there is no closed form solution (in general) for the roots. However, Newton's Method does converge quadratically.

I'm curious as to what you are using this for. This is not one of the typical computations done with Bezier curves.

Best wishes,
Stephen

@hrant: heh, thanks.

@sgh: You are absolutely correct, the convergence of Newton's method is much faster than bisection. However, Newton's method can fail to converge when the relationship is not approximately linear, which can definitely happen with cubic Bezier segments when the control points are "kinky." Bisection is much more robust in that case, as it's pretty much guaranteed to converge at _something_ in range of the solution.

One approach which might be more robust than Newton but converge faster than bisection is the secant method. Actually this has the added advantage that you don't need to analytically compute the derivatives, as well. I've used it quite a bit in my spline foo.

There are other approaches to the problem which could work, but they could get hairy. If you can decompose your beziers into circular arcs, then the problem reduces to computing the intersection between two circles, which is quite simple. Here's a reference on that:

http://itc.ktu.lt/itc354/Riskus354.pdf

And, what @sgh said, it's hard for me to imagine why you really need this.

Hope this helps.

QED. ;-)

But it's great to see we have at least a few more
math experts around here. I myself have a minor in
Numerical Analysis, but there's now more rust than metal...

hhp

Hi people,

thanks four your responses. Understanding them is already hairy for me.
So let me continue with answering the question to the why.
I'm working on a type design software plugin that illustrates curve speed on top of bezier outlines, live while editing outlines.
In order to calculate the amount of curvature I'm calculating on-curve points in equal distance, then calculating the angle between them. Just cutting a curve segment into equal parts using SplitCubicAtT doesn't work because distance and hence angle will change when a curve becomes tighter, so angle calculation is useless. They need to be in equal absolute distance from each other.

But, thinking about it, i just had another idea. When distance between on-curve points (returned by SplitCubicAtT) decreases with increasing curvature, there's already the numerical basis for my illustration, right?
Here's another problem, though: This might work only per segment. How to sync illustrations between segments, when an equal amount of splits per segment will always return different distances, since segment lengths differ?

Cool idea. Wouldn't the first derivative of
the equation give you this relatively easily?

BTW, related and perhaps helpful:
Do I remember correctly that there's a certain type
of spline equation that ensures constant (or maybe
controllable) velocity of change?

hhp

Dear Bezier masters,

I've tried to approach my problem (calculating curve speed) in a more general way, using the general cubic Bezier equation.
I've constructed the first (and to be sure, also the second) derivative, as suggested. Please correct me, if I made mistakes there. School was a looong time ago.
The function solveCubic return as the first argument p1234 (identical to the middle on-curve point calculated by the known splitCubicAtT function, I just skipped the other points for now), then the result of the first derivative, then the second.
All are vectors (or coordinates).

The segment used for the results posted below (with t as 0.1 steps) is a quarter of a circle, or a quarter of as close a circle as one can construct with Beziers. The first derivative should then have all equal (more or less) values, right, in case of a circle? In other words, curve speed should be steady at all positions in a circle.
But the results differ by 8%, even more in the second derivative. This doesn't look right. I've double-checked for a correct circle pie piece.

But maybe I have a misunderstanding of what to do with the results of the equations that are actually x/y-coordinates. So far I calculate the absolute value of the vectors (rightmost in the results, respectively).

import numpy, math

def solveCubic(p0, p1, p2, p3, t):
	p0, p1, p2, p3 = numpy.array((p0, p1, p2, p3))

	a = -p0 + 3.0 * p1 - 3.0 * p2 + p3
	b = 3.0 * p0 - 6.0 * p1 + 3.0 * p2
	c = -3.0 * p0 + 3.0 * p1
	d = p0
	
	# Cubic Bezier
	f = a*t**3 + b*t**2 + c*t + d
	
	# First derivative
	f1 = 3*a*t**2 + 2*b*t + c
	
	# Second derivative
	f2 = 6*a*t + 2*b
	
	return f, f1, f2


g = CurrentGlyph()
p1 = (g[0][0].points[0].x, g[0][0].points[0].y)
p2 = (g[0][1].points[0].x, g[0][1].points[0].y)
p3 = (g[0][1].points[1].x, g[0][1].points[1].y)
p4 = (g[0][1].points[2].x, g[0][1].points[2].y)

for t in range(11):

        
    f, f1, f2 = solveCubic(p1, p2, p3, p4, t / 10.0)

    print "t=%s" % (t/10.0), " -  f1=%s=abs %s" % (str(f1).ljust(17), int(math.sqrt( f1[0]**2 + f1[1]**2 ))), " -  f2=%s=abs %s" % (str(f2).ljust(13), int(math.sqrt( f2[0]**2 + f2[1]**2 )))

The results are:

t=0.0  -  f1=[-417.    0.]    =abs 417  -  f2=[ 162. -672.]=abs 691
t=0.1  -  f1=[-398.25  -64.65]=abs 403  -  f2=[ 213. -621.]=abs 656
t=0.2  -  f1=[-374.4 -124.2]  =abs 394  -  f2=[ 264. -570.]=abs 628
t=0.3  -  f1=[-345.45 -178.65]=abs 388  -  f2=[ 315. -519.]=abs 607
t=0.4  -  f1=[-311.4 -228. ]  =abs 385  -  f2=[ 366. -468.]=abs 594
t=0.5  -  f1=[-272.25 -272.25]=abs 385  -  f2=[ 417. -417.]=abs 589
t=0.6  -  f1=[-228.  -311.4]  =abs 385  -  f2=[ 468. -366.]=abs 594
t=0.7  -  f1=[-178.65 -345.45]=abs 388  -  f2=[ 519. -315.]=abs 607
t=0.8  -  f1=[-124.2 -374.4]  =abs 394  -  f2=[ 570. -264.]=abs 628
t=0.9  -  f1=[ -64.65 -398.25]=abs 403  -  f2=[ 621. -213.]=abs 656
t=1.0  -  f1=[   0. -417.]    =abs 417  -  f2=[ 672. -162.]=abs 691

I think the first (or second) derivative is conceptually wrong answer and what you are looking for is “curvature”, which you already compute through its “natural” definition … but you said it’s slow. There are also other types of formulas for computing curvature, but others might write more detailed answers.
When I saw your image I remembered this fine illustration by Tim Ahrens: What constitutes a "bad curve"?

I found it. It's an equation that involves the first and second derivative of the general Bezier equation.
See it in action: http://vimeo.com/32916950