The previous post dealt with solving three equations in three unknowns, however, one equation was trivial leaving two equations in two unknowns. This problem is similar and my guess is that the person emailing it to me is trying to fit an equation to some data. So, I’ll solve the requested problem, then comment on its application.
The person submitting the problem wanted to find the coefficients of a cubic polynomial satisfying the following conditions. Let p(x) = a + bx + cx2 + dx3.
p(0) = 0
p(1/4) = ∏/2
p’(0) = m1
p’(1/4) = m2
Instead of fitting a cubic polynomial to four points, this person wants to find the polynomial interpolating two points with specified slope at those two values. Seems to me this should really be a cubic Hermite curve, but more on that later. At the least, it’s a good exercise in setting up and solving a system of equations.
Now, p’(x) = b + 2cx + 3dx2, so
p(0) = 0 means that a = 0. This makes things quite a bit easier
p(1/4) = ∏/2 -> b/4 + c/16 + d/64 = ∏/2 or b/2 + c/8 + d/32 = ∏ or 16b + 4c + d = 32∏ .
p’(0) = m1 -> b = m1 . Fortunately, the easy initial conditions leave us with two equations in the remaining two unknowns c and d.
p’(1/4) = m2 -> m1 + c/2 + 3d/16 = m2 – m1 or 8c + 3d = 16(m2 – m1) .
Substitute the value of b into the equation for p(1/4) to obtain 4c + d = 16(2∏ – m1) = c1
Let c2 = 16(m2 – m1) = 8c + 3d. Solve the above equation for d and substitute into the second to yield
8c + 3(c1 – 4c) = c2 or 4c = c2 – 3c1 or c = (c2 – 3c1)/4 .
Since d = c1 – 4c, we have d = c1 – (c2 – 3c1) = 4c1 – c2 .
Given the coefficients, the polynomial can be evaluated efficiently in nested form. I think the issue with these problems is getting overwhelmed with all the conditions. Once you write it out and take it one step at a time, things become much easier, especially with the friendly conditions. It can often be easier to introduce additional temporary variables such as the c1 and c2 above instead of writing everything out in terms of initial variables and conditions.
My belief is that the person asking this question wanted to ‘fit’ a table of data with a cubic polynomial. The conditions were designed to force the polynomial to take a certain direction ‘out of’ the initial point and ‘in to’ the final point. The problem with polynomials of this form is that they want to oscillate. The higher the degree, the greater the tendency to oscillate. Just setting the derivative value at the endpoints does not guarantee the polynomial will follow that direction more closely as the derivative value increases. That’s essentially what a cubic Hermite curve does. The polynomial derived here may do a good job close to the endpoints, but don’t assume that means a good fit anywhere else.
In the previous post on parabolic scaling, we presumed that a quadratic polynomial was a reasonable model for the problem at hand. I hope this post helps some people with setting up and solving simultaneous equations and provides some insight into the thinking process regarding whether or not such a polynomial is a good model for a given problem.
This is a variation on a problem submitted to me recently. I suspect the original question related to scaling an object moving in a circular, elliptical, or some other path parameterized on an angle that varies between zero and pi. The scaling is applied in Actionscript and must satisfy the following criteria (Let S(θ) = scale factor at the angle, θ).
S(0) = 1/4
S(∏/2) = 3/4
S(∏) = 1
S(3∏/2) = 3/4
S(2∏) = 1/4
The question is how to derive a formula for the scaling that satisfies these conditions. This is the opposite of a more common situation in which one is given a functional representation and required to derived the necessary function parameters. In this case, we are given conditions but no direction on an appropriate functional representation. In such a case, we are free to choose the function. Actual choice may depend on aesthetic or other considerations.
First, notice the symmetry about pi. The problem can be reduced to one of finding a functional representation of S(θ) in [0,∏] If the input angle is greater than ∏, we can use reflection to generate the angle that is input to the scale function.
For purposes of illustration, a polynomial representation for S is used. Three conditions are provided in [0,∏], providing three degrees of freedom in selecting function parameters. This allows a quadratic polynomial to be used to represent S, i.e.
S = a + bθ + cθ2
The three coefficients a, b, and c are determined from the three conditions
S(0) = 1/4
S(∏/2) = 3/4
S(∏) = 1
The first condition implies a = 1/4, leaving us with two equations in two unknowns,
1/4 + b(∏/2) + c(∏2/4) = 3/4
1/4 + b∏ + c∏2 = 1
I won’t crank through all the math here (if too many people have problems, I’ll post the complete derivation later).
The solution is b = 5/4∏ and c = -1/2∏2
In the code, the angle should be reduced to [0,2∏]. If the reduced angle is greater than ∏, reflect about ∏ to create the actual θ value to input to the formula
s = a + b*(θ + c*(θ))
which evaluates the polynomial in nested form. The parabolic representation of scale is only one possible solution to this problem. If the input scale factors vary, it is possible to use Cramer’s rule, for example, to dynamically solve for the necessary coefficients.
Well, it’s official. Last night, I brought home a new MBP, 17″ . I’ll be loading up on software over the next month or two. I’m moving today, so I’ll be offline for a couple days. I might post some pics when I get the new office setup.
Yes, I’m a MAC
This problem, in a couple different variations, has been presented to me a few times over the past two months so I thought it might be worth a blog post. The problem ranges from drawing an aribtrary circular segment to the more general fractional circular area problem. Since the former is covered in the latter, the problem discussed here is how to dynamically draw a portion of a circle that represents some fraction of the circle’s area. Refer to the following diagram.
The green shaded area represents a segment of the circle with radius r. The general problem is given some multiplier, α in [0,1] how do we draw the green region so that its area is αAc, where Ac is the area of the circle. If α is less than or equal to 1/2, the problem reduces to drawing a circular segment at or below the horizontal axis passing through the center. For larger multipliers, we can locate the A and B points corresponding to a segment from the ‘top’ of the circle at a multiplier 1- α , drawing the complement of that segment.
Once the points A and B are identified, the outline of the circle is drawn with a sequence of quadratic Beziers just as in a wedge-drawing program with a line from A to B to complete the drawing. The quad. Bezier code for this example was extracted from my Singularity Wedge class.
To start the Bezier drawing, we need a start and end angle. Given the central angle of the sector, Θ, the start and end angles follow immediately. You can look up the area of the segment on the web and equate it to a multiplier of the circle’s area. This yields the equation
Θ – sin Θ = 2∏a .
This is not directly solvable for the central angle. If the constant term on the right is moved to the left side of the equation, then the problem reduces to finding a zero of a function. Ah, a numerical analysis problem … just what I like I like it even more that I’m about to move and was organizing some folders containing old NA notes and had some scribbling on a good starting value for Θ – sin Θ, namely the cubed root of the constant term with a small multiplier. So, Newton’s method should converge pretty quickly.
A standard Netwon iteration is used with f(Θ) = Θ – sin Θ – 2∏a and f’(Θ) = 1 – cos Θ . The computation of start and end angles corresponding to the A and B points as well as the quad. Bezier code to trace the relevant circle outline can be deconstructed from the example code.
The following diagram shows an example of a multiplier greater than 1/2. In the demo code, the slider is moved to vary the multiplier from 0 to 1.
The code is all AS in Flash CS4. No classes, just straight code on the timeline. You can modify the code, repackage it into classes, do whatever you like. Deconstruct and enjoy
As an aside, there is another approach to this problem that I like even better, but does not have the simple intro. to Newton’s method. If time allows, I’ll blog about that one later.