Google Answers Logo
View Question
Q: 3D Polynomial Fit, With Interpolation ( Answered 5 out of 5 stars,   0 Comments )
Subject: 3D Polynomial Fit, With Interpolation
Category: Science > Math
Asked by: larman-ga
List Price: $150.00
Posted: 11 Jun 2004 09:58 PDT
Expires: 11 Jul 2004 09:58 PDT
Question ID: 359732
My math lingo is a bit weak so I will try to explain the question clearly.

I have five 3D points (x,y,z) which I need to apply a fourth order
polynomial fit. The x,y,z values are Java double precision.
In simple terms, I want to create a curve fit across the five 3D points.
Then, I need to interpolate 29 new points between each of the five points,
following the curve that we created using the 4th order polynomial fit.

At the end of the exercise, I should have five 3D points, with 29 new
3D points between each that were interpolated from the polynomial
curve. Like this:

Point 1 
(29 new interpolated points)
Point 2
(29 new interpolated points)
Point 3
(29 new interpolated points)
Point 4
(29 new interpolated points)
Point 5

Resulting in 121 3D points (x,y,z) that represent a polynomial fit across 
the initial five points.

A satisfactory answer would be:

1. Some sample Java code that would produce the desired results above.


2. A formula that a reasonably intelligent person could translate to Java,
using only the intrinsic java.lang.Math functions found here:

Subject: Re: 3D Polynomial Fit, With Interpolation
Answered By: tox-ga on 11 Jun 2004 15:08 PDT
Rated:5 out of 5 stars
Hi larman!

Your question was rather interesting and, dare I say, fun to answer.

Here is the code for the program you requested:

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:

(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.


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
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.


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.


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,

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.

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,
larman-ga rated this answer:5 out of 5 stars and gave an additional tip of: $25.00
Tox has exceeded my expectations... This was my first Google.Answers
question and it was a tricky one. I decided to pay $150 because the
information was worth it, if answered correctly. Tox did a GREAT job..
My brain hurts when I think about all of the energy he put in. Not
only that, my question was 100% solved with zero clarification on my
part. In 10 hours from me posting the question!  Thanks a million Tox!

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy