View Question
Q: 3D Polynomial Fit, With Interpolation ( Answered ,   0 Comments )
 Question
 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. OR 2. A formula that a reasonably intelligent person could translate to Java, using only the intrinsic java.lang.Math functions found here: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Math.html Cheers!```
 ```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```
 larman-ga rated this answer: 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! :)```