View Question
Q: 3D Polynomial Fit, With Interpolation ( Answered,   1 Comment )
 Question
 Subject: 3D Polynomial Fit, With Interpolation Category: Science > Math Asked by: needshelp-ga List Price: \$100.00 Posted: 21 Mar 2006 14:47 PST Expires: 20 Apr 2006 15:47 PDT Question ID: 710220
 ```I have "n" 3D points (x,y,z) which I need to apply a Nth order (N < n) polynomial fit. The x,y,z values are Java double precision. In simple terms, I want to create a curve fit across the "n" 3D points. A satisfactory answer would be: 1. Some sample Java code that would input a file containing "n" lines of X,Y,Z data and then by asking the user for a new X,Y pair, and the polynomial order "N", present the result "Z".```
 ```There are many ways to do this. Good plotting programs often include fits and allow intearctive visualisation. Open Directory - Science: Math: Software: Graphing - MathGrapher - Mathematical graphing tool for 2D and 3D functions and data. Also includes statistical tools, nonlinear curve fitting, .. http://dmoz.org/Science/Math/Software/Graphing/ Gnuplot Not knowing details of you setup, I would recommend 'gnuplot' as easiest. It can be download compiled, ready to run for most platforms: About: http://www-128.ibm.com/developerworks/library/l-gnuplot/ FAQ: http://www.gnuplot.info/faq/faq.html This is a tutorial on 'fit' command Fitting with gnuplot -------- simple fit demo (2D curve y(x), 3D surface z(x,y) http://gnuplot.sourceforge.net/demo_4.1/fit.html http://nuclear.dj.kit.ac.jp/~ohta/gnuplot/fit.html http://www.softlab.ntua.gr/facilities/documentation/unix/gnu/gnuplot/gnuplot_21.html http://t16web.lanl.gov/Kawano/gnuplot/intro/plotfunc-e.html Your case: Fit 3D curve [x,y,z](s) or z(y) and y(x) ------------------------- Description of curve in a 3D space can be done in several ways: parametric form defines a point in E3 for each parameter s (s ranges from 0 to 1, e,g,) or as elevation z above a 2D cirve in x,y plane or etc .. In all cases. trick is to define a custom function, and an 'error term' which fit these two or three data sets at the same time. more about the fit command The fit command can fit a user-defined function to a set of data points (x,y) or (x,y,z), using an implementation of the nonlinear least-squares (NLLS) Marquardt-Levenberg algorithm. Any user-defined variable occurring in the function body may serve as a fit parameter, but the return type of the function must be real. Syntax fit {[xrange] {[yrange]}} '' {datafile-modifiers} via '' | {,,...} http://theochem.ki.ku.dk/on_line_docs/gnuplot/gnuplot_21.html Multiple datasets may be simultaneously fit with functions of one independent variable by making y a 'pseudo-variable', e.g., the dataline number, and fitting as two independent variables. See fit multibranch. multi-branch In multi-branch fitting, multiple data sets can be simultaneously fit with functions of one independent variable having common parameters by minimizing the total WSSR. The function and parameters (branch) for each data set are selected by using a 'pseudo-variable', e.g., either the dataline number (a 'column' index of -1) or the datafile index (-2), as the second independent variable. Example: Given two exponential decays of the form, z=f(x) , each describing a different data set but having a common decay time, estimate the values of the parameters So - in the case of parametric form, we are fitting 3 curves x(s) y(s) z(s) which we can wite is R(s) , R being a 3D point and minimizing error - a sum (over i) of squares (R.i - R(s))^2 OK? Hedgie``` Request for Answer Clarification by needshelp-ga on 27 Mar 2006 00:35 PST ```Unfortunately this does not qualify as an acceptable answer. A satisfactory answer would be: 1. Some sample Java code that would input a file containing "n" lines of X,Y,Z data and then by asking the user for a new X,Y pair, and the polynomial order "N", present the result "Z". Your answer contains no Java code, nor does it process the data in the manner specified.``` Request for Answer Clarification by needshelp-ga on 27 Mar 2006 00:43 PST ```tox-ga answered the question referenced below in a very acceptable manner. Exactly in the manner the user requested. If you wish to present an answer that does specifically what was asked, then do so. Otherwise I will ask Google to reopen the item for another answer. http://answers.google.com/answers/threadview?id=359732``` Request for Answer Clarification by needshelp-ga on 27 Mar 2006 01:11 PST ```One further point. An acceptable answer may NOT be a Java app that simply calls into a library such as MatLib. The code must operate as a standalone solution using only the basic Java libraries.``` Clarification of Answer by hedgie-ga on 27 Mar 2006 11:11 PST ```needshelp-ga It was not clear from your formulation 'Some sample Java code ..' that use of java is mandatory part of the specification. Sometimes it takes a bit of guessing and a bit of dialogue to figure out what the question is . I want to assure you that every researcher knows that asker can 'ask Google to reopen the item for another answer' It is hardly necessary to be reminding it, and rarely done in a first RFC. The problem usually is to figure out what is specifically asked, rather then lack of interest in customer's satisfaction. I see this is your firt use of GA - and so I am willing to give it another try - but, to prevent another misunderstanding and impatient reaction, I would like you to clarify this part as well: " by asking the user for a new X,Y pair, and the polynomial order "N", present the result "Z" .. " What pair? Is it not true that the input file is an order N and set of tripples? Can you perhaps post a short sample input file? Is parametric form I mentioned acceptable? Three polynomial x(s) y(s) z(s) all three polynomials x y and z have same order N ? Hedgie``` Clarification of Answer by hedgie-ga on 27 Mar 2006 11:42 PST ```The question (in more details) regarding this spec: " for a new X,Y pair, and the polynomial order "N", present the result "Z" .." is: If you get a Z for every (X,Y) pair , you have a surface = a 2D manifold in E3 if you want a curve (1D manifold in E3) you may want to enter s (one number between 0 and 1) and get (X,Y,Z) - a point in 3D space E3 So, are you seeking a surface or a curve?``` Request for Answer Clarification by needshelp-ga on 27 Mar 2006 12:58 PST ```A surface is the goal. The input set is ordered by the "X" values. If you need sample data, I will try to come up with some by tomorrow. Thanks. The original question did state "Java"``` Clarification of Answer by hedgie-ga on 28 Mar 2006 00:25 PST ```1) The original question said java source would do. It could have said ' java or fortran would do'. That is not same as 'it has to be in java', and 'has to be free source' etc. It also said you want "to create a curve fit" not a z(x,y) surface. 2) I now see your request as follows: ---------- I want a solution in java, which will takeas input n points in E3 (one tripple of double precsission floats per line) and integer N and do a LSQ fit with vertical offsets to a polynomial Z= Sum over i,j in 1,2, .. N ( a.i.j * X^i * Y ^j ) 3) Please review terminology of LSQ at -------------------------------------------------\\ Clarification of Answer by hedgie-ga on 15 Mar 2006 04:52 PST Thank you for your clarification. I do believe that with this extra info I can answer your question: Let's get out terminology straight: The Method of Least SquaresLSQ methods http://answers.google.com/answers/threadview?id=706840 -----------------------------------------------------------// 4) the question could continue like this I am /am not a java programmer, so I can add/cannot interface to a java library I understand / do not that java is not efficient for numerical calculation, but speed does not matter (n and N are small, and it is a one-time job) 5) I also want an interpolation program which will use a fitted polynomial to provide Z for any (X,Y) (as a separate program, or using some command to separate (xyz) set from (XY) set. I understand concept of splines, and the parametric definition (e.g. a sphere has two z's fro some (X,Y) pairs and none for others, but I want polynomial given above, and minimilasation is unconstrained in x,y plane, or data set is such that [x.i y.i] points of the tripples are in rectangle xmin- xmax ymin.. ymax (naturally or constrained .) I do/ do not know calculus , my goal application is .. etc. 6) I suggest that you read my answer http://answers.google.com/answers/threadview?id=701289 then drop the arguments about what you and how well you said it in initial formulation. Then please, formulate the whole answer from start, giving me more info. I will withdraw the answer if you decide not to respond by April 5th. We are here to serve our customers and I will welcome your cooperation. Hedgie``` Request for Answer Clarification by needshelp-ga on 28 Mar 2006 01:12 PST ```Ok - restated in your suggested format: I want a solution in java or c++, which will take as input n points in E3 (one tripple of double precsission floats per line) and integer N (polynomial order) where N < n, and do a LSQ fit with vertical offsets to a polynomial Z= Sum over i,j in 1,2, .. N ( a.i.j * X^i * Y ^j ) I am not a super-proficient programmer, nor do I want a front end to a third party or non-source library. I understand that java is not efficient for numerical calculation, but speed does not matter (n and N are small). The input data will already have been sorted such that Y0 <= Y1 <= Y2.. and when Yn == Yn+1, the data will be further ordered such that X0 <= X1 <= X2... After the fit is run, the application should prompt the user for a X,Y pair and perform the interpolation displaying the result "Z". This is a bench-test situation and in its final form (as re-coded by me) this will not be an interactive program but a function that will be called by my main application. Only for validation testing will I be using the X,Y,Z file as the input source. I presently have c++ code that I put together years ago using Gauss-Jordan elimination? for the same type of work on 2D curve data. I can email the code to you for that if it would be of assistance. Im sorry for the poor presentation of the original question. There will be a 100% tip if we get this going :)``` Clarification of Answer by hedgie-ga on 28 Mar 2006 22:14 PST ```That is a better, MUCH better, formulation of the problem. RE: "can email the code to you for that if it would be of assistance." That is not necessary. ( And BTW, GA rules do not allow direct contact with customers, via email etc see: Should I post my email address to Google Answers if someone asks for it? http://answers.google.com/answers/faq.html#postemail ) It looks like you still have some concerns about whether this is hard to do; It is not much more difficult than fitting a curve. I will describe several ways of doing this. Please start by looking at this animated gif, which shows a fit to N points. http://www.wxres.demon.co.uk/wsts/computing/maths/datafit/linfitnd1.gif This fit was made using 1) WSTS Data-Fitting Software This is a suite of programs to fit functions to discrete data. The programs are written in C++ using the mathematical library. See list in the link for what is included. ) http://www.wxres.demon.co.uk/wsts/computing/maths/datafit/ look in particular at: LINFITND: ND fitting of a linear combination of arbitrary functions LINFITND finds the best least-squares fit of a set of arbitrary functions to data. The data may include weightings for each point. The program calculates the fitting coefficients, the residual of the fit (sum of squares of deviation from each point), the determinant of the fitting equation (indicating when the fitting process may run into trouble if the problem is ill-conditioned) and the deviation in each point. Allowable functions include any of the Realfunctionnd class in the WSTS C++ maths library. http://www.wxres.demon.co.uk/wsts/computing/maths/datafit/index.html#linfitnd 2) Gnuplot (This is the most strongly recommended method.) That plot is made with a gnuplot, the same gnuplot which I mentioned before, and which can do the fit of a surface also. Fitting a surface is easier than fitting a curve in 3D. Please download Gnuplot and run this simple example: "To fit a function with two independent variables, z=f(x,y), the required format is using with four items, x:y:z:s. The complete format must be given--no default columns are assumed for a missing token. Weights for each data point are evaluated from 's' as above. If error estimates are not available, a constant value can be specified as a constant expression (see plot datafile using), e.g., using 1:2:3:(1) " g(x,y) = a*x**2 + b*y**2 + c*x*y FIT_LIMIT = 1e-6 fit g(x,y) 'surface.dat' using 1:2:3:(1) via a, b, c as described here: http://theochem.ki.ku.dk/on_line_docs/gnuplot/gnuplot_21.html The file (sample is included) see also: http://scs.ictp.it/manuals/gnuplot/gnuplot_78.html http://www.ap.stmarys.ca/~dclarke/PHYS3437/handouts/gnuplot.pdf. The Gnuplot program is written in c (subset of c++) and actually is a merge of the two programs, one for plotting and one for fitting: Carsten Grammes has written a fitting program which goes together with gnuplot; it is called gnufit and is available from the official gnuplot sites, as the files gnufit12.info, gnufit12.tar.gz (source) and gft12dos.zip (MS-DOS). It has been merged into gnuplot 3.6. http://www.netsw.org/graphic/plot/gnuplot/contrib/gnuplot.FAQ As I said before, there are many ways to do this, and reasonable ways are likely to use the same workhorse. Gnuplot is open source software (GPL). It is easy to install on any platform ( which one are you using?) and it works. The first task is to evaluate this to see whether it fits your needs. The easiest to start with for your evaluation are: here: http://www.gnuplot.info/ http://www.gnuplot.info/download.html After program is installed (which takes few minutes), you my run the demos which come with it, by saying gnuplot surface1.dem gnuplot surface2.dem then proceed to fit command, using any file of quadruples surface.dat. Sorting of the data is not important.: It is a linear LSQ problem and so any program which does it gnuplot will calculate sums over i if products X.i* Y.i etc, i.e. (R = [x,y,z]) and do a matrix inversion. I do not have "stand alone" program at this time, which does exactly what you specified. Even Gnuplot has some limitations (it wants quadruple on each line) X Y Z weight and its command language does not support arrays: You have to specify the test function g(x,y) = a*x**2 + b*y**2 + c*x*y + ... + f*x^5*y^3 For testing purposes that is sufficient, plus you have the benefit of instant visualization. When you have downloaded and compiled the gnuplot source, you already have all the routines needed to do the fit, routines you can use in your own program, subject to GPL. There are other ways, than gnuplot. Standard libraries, usually have demo calling programs and tutorials and have been ported to different platforms and translated to all languages (fortran c, c++ ..) 3) Even translated into java as well: http://www1.fpl.fs.fed.us/optimization.html 4) NAG library is one of the best - but not quite free (It is a polished version of the free library). Chapter e02 ? Curve and Surface Fitting http://www.ualberta.ca/CNS/RESEARCH/NAG/Clib/pdf/genint/libconts_cl05.pdf. The NAG C Library is a collection of over 250 high-quality routines for mathematical and statistical computation. The library is written in C, and is based on the same numerically sound techniques used in the NAG Fortran Library. The NAG C Library is available on centrally administered Unix systems (tower and ebor), and also on the Windows 95 PC network. On the Windows 95 network, the NAG C library Mark 5 is installed as a 'dynamic link library' (DLL), so programs making use of it will be compact, but do need to be compiled with some special switches. http://www.york.ac.uk/services/cserv/help/programming/pages.sup/nagc-w95.htm 5)Of possible interest http://www.amazon.com/gp/product/084937376X/102-7446460-2049751?v=glance&n=283155 with free code: Numerical Recipes code Download now in C++, C, or Fortran. Windows, Linux, Macintosh versions www.nr.com http://users.physics.uoc.gr/~kele/codes/lsq.htm This book describes a similar, somewhat better code than Numerical Recipe http://www.amazon.com/gp/product/0521750334/ref=pd_lpo_k2a_1_img/102-7446460-2049751?%5Fencoding=UTF8 So, please Select one way, evaluate it, and if you need help with writing a simple front end, which does specifically what you want (e.g. read triples, not quadruplets), do not hesitate to post another RFC.```
 ```This isn't in Java format, but it describes the procedure that you probably want to implement: http://mathworld.wolfram.com/LeastSquaresFittingPolynomial.html```