Cubic Splines help

Having been completely perplexed by VBAHack's comprehensive tutorial regarding fitting cubic spline curves to data points, I have a question that perhaps VBAHack would be able to answer.

I have 4 data coordinates and I wish to (programatically) interpolate a curve between the middle two of them (see screenshot attached)...

(1, 1.5), (2, 0.5), (3, 2.5), (4, 3.5)

I am not familiar with advanced mathematics or matrices though (which is where I had trouble with the tutorial, I'm certainly no mathematician :)), believe me I did try quite hard to understand VBAHack's tutorial but I soon got lost in the mathematical complexity.

I'd be much obliged if someone could walk me through how to convert those 4 coordinates into a polynomial expression of the sort that I can just plug x values into and get y values out of it.

I don't want code, I can work that part out if I could come to understand the method to obtain the polynomial from the 4 coordinates, which I guess would be something like:
y=ax⁴ + bx³ + cx² + dx + e

The curve I end up with doesn't have to be particularly accurate, as long as it looks about right.

Sounds like all you want to do is find a single polynomial equation that goes through all four points. If that's true, it would be a cubic:

y =ax³ + bx² + cx + d

Since you have 4 points (x₁, y₁, etc.), you can write the following 4 equations:

y₁ = ax₁³ + bx₁² + cx₁ + d
y₂ = ax₂³ + bx₂² + cx₂ + d
y₃ = ax₃³ + bx₃² + cx₃ + d
y₄ = ax₄³ + bx₄² + cx₄ + d

By using the actual values of x₁, y₁, etc., you end up with 4 equations in 4 unknows:

1.5 = a + b + c + d
0.5 = 8a + 4b + 2c + d
2.5 = 27a + 9b + 3c + d
3.5 = 64a + 16b + 4c + d

To find a, b, c, d you can use what's called Gauss Elimination. The link below is a step by step example using 3 equations and 3 unknowns. The procedure with 4 equations is the same, though a bit longer.

http://tutorial.math.lamar.edu/Class...hreeVrble.aspx

I'm beginning to understand now.

Paul Dawkin's Ebook on the subject is actually very understandable.

I think I'll need to use a augmented matrix (4 rows, 4+1 columns) to solve the simultaneous equations in order to find the "y=..." expression I require.

I ran through a few augmented matrix examples today and I actually understand them a lot better than the long-winded methods that they tried to teach me at high-school.

Thank you for your help, I'll let you know how I get on :)

Of course, there's more than one way to skin a cat--Cramer's rule is another way to solve your system. The Wikipedia article gives the 3x3 case explicitly. 4x4 is very similar. The advantage of Cramer's rule to augmented matrices and Gaussian / Gauss-Jordan Elimination is that it's deterministic--you know exactly what steps will be taken ahead of time. This may well make it easier to code. The disadvantage of Cramer's rule is that, for large matrices, it becomes extremely slow.

And to check your answer, there are online solvers like:

http://wims.unice.fr/wims/wims.cgi?s...ef&+cmd=resume

I'll use the Gauss-Jordan method because I will probably want to use higher-order polynomials elsewhere in my application.

Thanks for the help guys.

I also need to curve fit a low order polynomial through 4 (x,y) points. I appreciate (and understand) the Gauss Elimination method.

My question is, "is there a function in Visual Basic 6 that I can use which finds the coefficients for me"?. I guess I'm thinking back many years to school where I think I remember "determinants" or something like that.

I've managed to finish my algorithm at last (see screenshot).

It uses a small number of random values to generate a few polynomial curves which are then evaluated for a few rows evenly spaced through the map (but with large gaps between). Then another pass to use values from the interpolated curves from the previous pass to fill in the entire map vertically, to give a smooth set of curves that look vaguely organic and natural, like landscape.

This is to be used as a terrain randomiser for a video game.

Depending on your game, using nice, smooth functions will give your terrain a very rounded look. I'm curious, do you want mountains as well?

Also, interestingly, the algorithm you described is a special case of a general surface fitting algorithm I described not long ago. My generalizations allow for arbitrarily many spacial dimensions instead of just 2, an arbitrary fitting function instead of just a cubic spline, and arbitrary high-dimensional sample grids. Of course, that's all overkill for your purpose :).

Interesting... although you lost me at "n-dimensional Surface Fitting through Successive Coordinate Line Interpolation on a Finite Lattice". My brain rebooted. Although it does kind of sound like what I was doing, if a lattice is a grid of some sort.

Yeah, my map does seem to have some patterns to it, the screenshot I posted does seem to fit into a 4x4 grid pattern. So I altered the spacing of the random points but it seemed to make little difference to the outcome.

Yeah... maybe the title was overly descriptive. In two dimensions, the lattice I described does turn into a "grid". You could try adding randomly noise to your map, to make it a little more realistic. A cubic spline usually gives a very smooth fit, but sometimes it's just too smooth to look realistic.