Andrew Que Sites list Photos
Projects Contact

No articles for week of February 01, 2012

Falling back to closest date.

December 12, 2011

Algebraic Curve with Curvature

Tangent location

Now, some actual application of what I learned in calculus 3. The previous demo was on curve fitting algebraic curves. Now that this is done, it's time to add the tangent, normal, and curvature circle. To start, we will need the tangent line of this function. Note that the function is now two functions, one for the x-coordinate, and one of the y-coordinate. This can be expressed using a vector function, f( t ) = ( X( t ), Y( t ) ). To get the tangent line, we still need a rise over run based on the derivative at some point a. Well, the rise is based solely on Y( t ), and the run solely on X( t ). So the resulting slope then becomes Y '( a ) / X '( a ). The tangent line function itself is y = [ Y '( a ) / X '( a ) ][ x - X( a ) ] + Y( a ). The normal line is again just a 90-degree rotation of the tangent line, easily obtained by taking the negative inverse of the slope. The curvature now requires both the x and y components of the function, and the full function is κ( t ) = [ X '( t ) Y ''( t ) - Y '( t ) X ''( t ) ] / [ X '( t )2 + Y '( t )2 ]2/3. It looks a little messy, but the reality is the function just involves the first and second derivatives—it's not that bad.

The scroll bar selects the location to place the tangent line, normal, and curvature circle. Since the curve is no longer a function and can double back on itself, I could no longer use the floating bar above the image. If you adjust the curve, you may notice the curvature circle is sometimes on the outside of the function, looping in the wrong direction. This is one irritating item I've been trying to fix. It seems from the fact the normal does not always point inward, and I have thus far been unsuccessful in figuring out how to make this happen. It does, however, give me something else to work on.


For the last several days I've been trying to think about how to advance my curve fitting system to a 2-d system. Right now, the curve is a 1-d polynomial function, and functions can not overlap. I wanted a 2-d parametric function. Applying the least squares system of curve fitting to this seemed like it should be possible, but I wasn't sure how to start. After several days of mulling the idea I found myself sitting in the chemistry building library.  I happened to glance an angelic looking girl sitting at a table not far from me. I suspect she was a muse, because moments latter I figured out a solution to this problem.

My function needs to be in terms of one parameter, say t. As t changes, a path for x and y are traced out. So now, if I have points (a,b), (c,d), and (e,f) I can create a function that traces a path between them using a function based on t. I do this by creating two functions, one for the path that traces the points in x, and one that traces a path in y. Both functions take t as a parameter. So fx(t) will pass through the point (t1,a), (t2,c), and (t3,e), and fy(t) will pass through (t1,b), (t2,d) and (t3,f). The resulting function is then f(t) = ( fx(t), fy(t) ). The values of t at each point don't matter, as long as they are the same for the set of fx and fy equations. All that is needed is to use the same system I have for my normal curve fitting, but generate two sets of coefficients—one for x, and one for y—based on the modification above. The main loop, rather than y as a function of x, changes so x and y are functions of t.

The implementation was fairly quick, but I could no longer use my XY Plot library—it can't do parametric functions. For my implementation, t runs from 0 to 1, and the points it passes through are divided equally amongst this run. The curve itself is drawn with a series of lines calculated at various locations. I used 200 locations, and the curve looks smooth in this image regardless of the point orientation.

Turning on the equations will display the equations for fx and fy in the left and right columns respectively. Order of the points matters because this is now a parametric function. Right now you can not smoothly join the head and tail of the function—I may have to find my muse again to figure this out!

   Today's demo is again about curvature.  This time I've added normal vector (in blue) next to the tangent line (in green), and the circle (in purple) representing curvature at the tangent location.  The curvature on any circle is the same at every point.  What this circle then shows is an equivalent circle with the same curvature as the point on the function.  With the driving example, the side-to-side G-force experience driving at that point on the curve would be the same as if you were on a circle pictured.
   Part of this calculation involved making a line segment for the tangent and normal lines.  I wanted the segment for these lines to be a constant length.  When I looked at the problem, I saw a use for polar coordinates.  This is because I had a center point, and I wanted to draw a line out some constant distance outward from that point.  In polar coordinates a vector is expressed as a radius from the origin, and an angle.  I had the radius, I just needed direction.
   The direction of this line has to come from my line equation.  That equation is m x + b, where m is the slope and b is the y-intercept.  The slope is expressed as rise over run, or y / x.  When looking at the triangle formed from this, it was clear the angle formed were the sides opposite (rise) and adjacent (run).   Opposite over adjacent is the tangent of the angle.  Thus tan( θ ) = m. which means θ  = tan-1( m ). 
   To convert back from polar coordinates we use the point ( r cos( θ ), r sin( θ ) ) where r is the radius.  Plugging in the calculation for the angle θ results in ( r cos( tan-1( m ) ), r sin( tan-1( m ) ) ).  With some trigonometric identities, this becomes ( r / 1+m2 , m r / 1+m2 ).  I could likely have figured this out using Pythagorean theorem but my method still worked. 
   To get the normal vector, one just has to rotates the tangent line 90 degrees.  For this, some matrix math can be used, but I cheated and looked it up.  Turns out to rotate a line function in the form m x + b, you just modify m such that m = -1 /  m.  So enjoy the demo!
    Today's demo is much the same as yesterday's, with one change.  Rather than getting curvature for a single point, the curvature is now displayed as a color gradient behind the graph.  This gives a better real-time indication of how curvature changes with the shape of the function.  In the graph, the darker blue means higher curvature.   Notice how curvature always increases around a local minimum or maximum.  A graph that has higher peaks and valleys also has much faster transitions in curvature.  That is, the curvature is relatively low between local min/max, but close to the min and max values for curvature quickly increase.
   This is really the first time I've used anything I've learned from calculus III, although I technically touched on curvature in calculus II.  I have yet an other demo planned about curvature, but we'll see if I have enough knowledge and time to complete it.  So stayed turned for more math...

An other demo similar to yesterday, but with one addition: the calculation of a value called curvature. In effect, the larger this value, the sharper the curve. Think about the function graph as a road. If you are driving down the road quickly and had to make the turns required to stay on the road, curvature would be related to how much sideways G-force you would feel through these turns. You can move the points around to make functions with varying degrees of curvature, then move the red line over the point in the function you would like to measure curvature. Notice the green tangent line. In locations with small curvature values, the tangent line runs closer to the function for a longer span than for locations with high curvature.

Calculating curvature required adding some calculus functions to my curve fitting script. First, let's examine the function for curvature.

We need the first and second derivative of the function (f) for this computation. Since the curve is always a polynomial, the derivative function isn't too difficult. The function always has this form:

Where n is the number of terms in the polynomial, and c is an array of coefficients. The first derivative of the function:

And the second derivative:

A pattern emerges, and the mth derivative of the function f is:

In software, this is quite easy to compute and didn't require a lot of changes to the loop for calculating the function at a point.

And by the way, Happy December!


The above demonstration is on tangent lines. This is a concept learned early in calculus. A tangent line is a linear representation of an equation at some point. The closer to the point of origin, the closer (i.e. the less error) the function is approximated.

In this demo, the red bar can be moved to select the location at which the tangent line will be calculated. The resulting graph will show the calculated tangent line in green. As with previous math demos, the black dots may be moved around to modify the function, and more or less points can be used.

The equation for the tangent line at some point a is g( x ) = m ( x a ) + b, where m = f '( a ), b = f( a ), and f is the function. This demo creates a polynomial function for f based on the points the function needs to intercept. The resulting polynomial function can be expressed:

f( x ) = c0 + c1 x + c2 x2 + c3 x3 + … + cn xn

The derivative is then:

f '( x ) = c1 + 2 c2 x + 3 c3 x2 + … + n cn xn-1

This is quite easy to compute. So the slope (m) of the line is based on the derivative, and the intercept (b) is based on the root function.

The demonstration is (I hope) the first part of a more complected demonstration I plan on doing latter on.

   I've been playing with VirtualBox for sometime, and I learned a new fetcher I like. runs on a Ubuntu-based web server. When developing the PHP code for demos I've made in the past, I've always had the server next to me. However, without instant access to the server, I needed a way to have a LAMP setup running. I decided VirtualBox was the answer. Using “Host-only networking” I was able to use a Ubuntu virtual machine, and setup a LAMP server visible to the local host. I was able to use my local web browsers to develop the PHP and Javascript just as if I had sitting next to me.
   The picture is one in a series of shots taken at Disaster House.