Google Answers Logo
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".
Answer  
Subject: Re: 3D Polynomial Fit, With Interpolation
Answered By: hedgie-ga on 24 Mar 2006 03:11 PST
 
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]}} <function> '<datafile>'
         {datafile-modifiers}
         via '<parameter file>' | <var1>{,<var2>,...}


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.i * r.j>  (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.
Comments  
Subject: Re: 3D Polynomial Fit, With Interpolation
From: kime1r-ga on 23 Mar 2006 10:54 PST
 
This isn't in Java format, but it describes the procedure that you
probably want to implement:
http://mathworld.wolfram.com/LeastSquaresFittingPolynomial.html

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 answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


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