Hi larman!
Your question was rather interesting and, dare I say, fun to answer.
Here is the code for the program you requested:
http://www.maxlin.ca/tos/ga/QuarticFit.java
To run it, compile it and use
java QuarticFit x1 y1 z1 x2 y2 z2 x3 y3 z3 x4 y4 z4 x5 y5 z5
To ensure the interpolation works correctly, enter the points in order
of increasing x. Of course, this could be easily made unnecessary by
sorting the input.
It works by performing a partial regression analysis on each
dimension, using the least-squares method. It produces two quartic
polynomials that describe a 3D curve parametrically. To create the
interpolated points, it equally spaces (along the x-axis) 29 points
between consecutive input points (which is why they should be in
order) and then uses the parametric equations to evaluate their y and
z coordinates.
The polynomials are determined by using Gaussian-Jordan elimination on
a matrix to solve for the coefficients. The entries of the array are
determined by finding a general solution to the polynomials and taking
partial derivatives to minimize the distance between the curve and the
input points. A full derivation of this method is explained very well
in the following text:
http://www.ce.utexas.edu/prof/mckinney/ce311k/handouts/Regression.pdf
(A general form of the matrix is found at the top of page 8,
preceeding that is the derivation.)
If you have any questions about how the program or regression works,
or would like some help changing the program or getting it to work on
your computer, please feel free to ask! Use the 'Request
Clarification' feature so that I can do my best to help you before
closing and rating this answer.
Cheers,
tox-ga |
Request for Answer Clarification by
larman-ga
on
11 Jun 2004 15:48 PDT
Hi Tox, this is absolutely perfect. I compiled and ran the code with
some simple points: 10,10,10,20,20,20,30,30,30,40,40,40,50,50,50 and
the results were exactly as expected. Two things, I won't have time
until this weekend to look at the curve results- most important to me
is that it produces a 4th order curve similar to what is produced
here:
http://www.wam.umd.edu/~petersd/interp.html
Simply click 5 points, then move them around to see the behavior.
If you tell me that it works that way, I will go ahead and close the
question and gladly include a $20 tip.
Secondly, now that I have your source, can you remove it from the
site? I'm not the only one working on the problem and don't want to
make it too easy for my competitor. :) I didn't look at all of the
terms-of-use, so if that's against the rules, I totally understand.
Regards,
-LarMan
|
Clarification of Answer by
tox-ga
on
11 Jun 2004 16:34 PDT
Hi larman,
I'm glad you're satisfied with the problem. I have went ahead and
removed the source code as you requested.
Also, the curves which my program produces are definitely of fourth
order (also known as a quartic).
I should note, however, there is a small difference between the site
you sent me and the program I have produced. That site uses what is
known as Lagrange Interpolation to find the quartic which exactly
passes through the given 5 points. This curve is unique; only one
exists. Since you mentioned that you wanted a 'fit', I used
statistical techniques to find a quartic curve. These two techniques
produces curves which are almost exactly the same. When you consider
the error that naturally results from performing math using floating
point numbers, they are essentially the same. I doubt you will be
able to notice any difference.
Lagrange Interpolation takes n points and perfectly fits them with a
polynomial of degree n-1. Regression techniques generally do not fit
perfectly, but do so very closely with the advantage being that given
n points, you can fit with a polynomial of degree less than n-1. In
the case where you want to regress n points to a degree n-1 polynomial
(as is the case with your request), the two techniques produce either
exactly, or almost exactly the same curve.
So, in short, this program definitely does use a 4th order curve and
produce extremely similar results to the site you sent me, and the
source code has been taken down as per your request.
Cheers,
tox-ga
|
Request for Answer Clarification by
larman-ga
on
11 Jun 2004 17:44 PDT
Thanks Tox, sorry I missed the "4th order = quartic".. As I said, my
math ling isn't the strongest. I really appreciate your exceptional
work, you are a true professional. Likewise, I tested the 4th order
curve and it is working perfectly. Damn fine work, man! I have
included an additional $25 tip so go buy yourself a drink. :)
|
Clarification of Answer by
tox-ga
on
11 Jun 2004 20:50 PDT
Hi LarMan!
Thank you for the kind comments and the generous rating/tip! I'm glad
your first Google Answers experience was an enjoyable one. Always
glad to be of help.
Best regards,
Tox-ga
|
Request for Answer Clarification by
larman-ga
on
14 Jun 2004 12:43 PDT
Hi Tox, I've posted a second question that I would like for you to
consider answering.
Cheers,
-LarMan
|
Clarification of Answer by
tox-ga
on
14 Jun 2004 13:29 PDT
Hi there,
Just wanted to let you know that I saw that question and will work on
it tonight when I get home.
Best regards,
Tox-ga
|
,
0 Comments
)