Typophile - Comments for "To the Math Masters: Looking for inverse function of SplitCubicAtT + Pythagoreic Triangle"
http://typophile.com/node/86965
Comments for "To the Math Masters: Looking for inverse function of SplitCubicAtT + Pythagoreic Triangle"enI found it. It's an equation
http://typophile.com/node/86965#comment-485793
<p>I found it. It's an equation that involves the first and second derivative of the general Bezier equation.<br />
See it in action: <a class="freelinking external" href="http://vimeo.com/32916950" rel="nofollow">http://vimeo.com/32916950</a></p>
Thu, 01 Dec 2011 10:23:58 +0000yanonecomment 485793 at http://typophile.comI think the first (or second)
http://typophile.com/node/86965#comment-485161
<p>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.<br />
When I saw your image I remembered this fine illustration by Tim Ahrens: <a href="http://typophile.com/node/39705#comment-243972" rel="nofollow">What constitutes a "bad curve"?</a></p>
Thu, 24 Nov 2011 14:33:47 +0000mihacomment 485161 at http://typophile.comDear Bezier masters,
I've
http://typophile.com/node/86965#comment-484918
<p>Dear Bezier masters,</p>
<p>I've tried to approach my problem (calculating curve speed) in a more general way, using the general cubic Bezier equation.<br />
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.<br />
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.<br />
All are vectors (or coordinates).</p>
<p>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.<br />
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.</p>
<p>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).</p>
<pre>
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 )))
</pre><p>
The results are:</p>
<pre>
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
</pre>Tue, 22 Nov 2011 18:38:14 +0000yanonecomment 484918 at http://typophile.comCool idea. Wouldn't the first
http://typophile.com/node/86965#comment-483059
<p>Cool idea. Wouldn't the first derivative of<br />
the equation give you this relatively easily?</p>
<p>BTW, related and perhaps helpful:<br />
Do I remember correctly that there's a certain type<br />
of spline equation that ensures constant (or maybe<br />
controllable) velocity of change?</p>
<p>hhp</p>
Sat, 05 Nov 2011 21:56:53 +0000hrantcomment 483059 at http://typophile.comHi people,
thanks four your
http://typophile.com/node/86965#comment-483058
<p>Hi people,</p>
<p>thanks four your responses. Understanding them is already hairy for me.<br />
So let me continue with answering the question to the why.<br />
I'm working on a type design software plugin that illustrates curve speed on top of bezier outlines, live while editing outlines.<br />
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.</p>
<p>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?<br />
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?</p>
<p><div class="imageWrap"><img src="http://typophile.com/files/speedpunk_6263.png" /></div></p>
Sat, 05 Nov 2011 21:52:39 +0000yanonecomment 483058 at http://typophile.comQED. ;-)
But it's great to
http://typophile.com/node/86965#comment-483056
<p>QED. ;-)</p>
<p>But it's great to see we have at least a few more<br />
math experts around here. I myself have a minor in<br />
Numerical Analysis, but there's now more rust than metal...</p>
<p>hhp</p>
Sat, 05 Nov 2011 20:59:42 +0000hrantcomment 483056 at http://typophile.com@hrant: heh, thanks.
@sgh:
http://typophile.com/node/86965#comment-482981
<p>@hrant: heh, thanks.</p>
<p>@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.</p>
<p>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.</p>
<p>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:</p>
<p><a href="http://itc.ktu.lt/itc354/Riskus354.pdf" title="http://itc.ktu.lt/itc354/Riskus354.pdf">http://itc.ktu.lt/itc354/Riskus354.pdf</a></p>
<p>And, what @sgh said, it's hard for me to imagine why you really need this.</p>
<p>Hope this helps.</p>
Fri, 04 Nov 2011 21:16:45 +0000raphcomment 482981 at http://typophile.comThe cubic Bezier can be
http://typophile.com/node/86965#comment-482785
<p>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.</p>
<p>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.</p>
<p>I'm curious as to what you are using this for. This is not one of the typical computations done with Bezier curves.</p>
<p>Best wishes,<br />
Stephen</p>
Thu, 03 Nov 2011 05:28:53 +0000sghcomment 482785 at http://typophile.comFrom what I understand there
http://typophile.com/node/86965#comment-482694
<p><cite>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.</cite></p>
<p>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.</p>
<p><div class="imageWrap"><img src="http://typophile.com/files/circle_5878.gif" /></div></p>
Wed, 02 Nov 2011 15:33:16 +0000butterickcomment 482694 at http://typophile.comYou can ask the question on
http://typophile.com/node/86965#comment-482682
<p>You can ask the question on math forum: <a href="http://math.stackexchange.com/" title="http://math.stackexchange.com/">http://math.stackexchange.com/</a>. 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.<br />
In case of unusual bezier segments there may be more (maybe even up to 4?) resulting points with equal distance to the P1.</p>
Wed, 02 Nov 2011 14:02:07 +0000mihacomment 482682 at http://typophile.comJust ask Raph Levien.
hhp
http://typophile.com/node/86965#comment-482653
<p>Just ask Raph Levien.</p>
<p>hhp</p>
Wed, 02 Nov 2011 05:03:51 +0000hrantcomment 482653 at http://typophile.com