Interpolation between Bezier curves
in [Fortran]
|
Prev: mpi conditional point to point communication
Next: How to control/prevent cast between from complex to realvariables
From: deltaquattro on 19 Feb 2010 08:49 On 16 Feb, 20:46, GianLuigi Piacentini <ggpi...(a)tin.it> wrote: > deltaquattro wrote: > > Hi, > > > I have two different functions f(x) and g(x) described as > plane Bezier > > curves, say of fourth degree: > > > [f] =[(Pi_x,Pi_y)] > > [g] =[(Qi_x,Qi_y)] > > > with i=1..5. I would like to compute some samples of a third > curve > > h(x)=f(x)/g(x). Right now, I'm computing h by calculating f > and g at > > many points, say 21 equispaced values of the parameter t: > > > t=[0,....19/20,1] -> (x_i,f(x_i)); (y_i,g(y_i)) > > > Clearly, x_i and y_i will not in generally coincide, so I > interpolate > > the values of g at the abscissae of f and I compute 20 > samples of h as > > (x_i, f(x_i)/g_interp(x_i)). However, I have two problems: > > > 1) since I have the Bezier nodes, I'd like to somewhat > interpolate > > them and then compute h, instead than evaluating f and g on > a refined > > grid and then computing h. It seems to me that I'm wasting > cpu time > > and information. Is there a way to do that? > > 2) even if I stick to my expensive sampling -> interpolation > > procedure, it won't always work. The reason is that, because > of > > possible errors in the input, sometimes > > > P1_x <> Q1_x or P5_x <> Q5_x > > > i.e., f and g are not defined exactly on the same interval. > So I am > > not able to interpolate the g samples to the abscissae of > the f > > samples. How can I solve this? Thanks, > > > Best Regards, > > > deltaquattro > > You could extrapolate the curves a little, so that their > definition interval will be equal (I think that the book of > Farin or that of Mortenson explains the math). > Many years ago, when I watched colleagues working with similar > problems, I remember that they used splines defined as y=f(x). > I used piecewise linear interpolation (again in the form > y=f(x)) since its precision was enough given the > uncertainities in the data. > Given that you want h(x), my opinion is that there is no point > in having x as a (parametric) function, instead of the > independent variable. > > Hoping this helps... > > G.L. Piacentini Ciao GianLuigi, bet we're originally from the same country :) I was afraid of the risks of extrapolation, so I chose to compute h only on the intersection btween the intervals on which f and g are given: I see that in meantime Arjan suggested the same solution. Thanks for the suggestion of using splines, which was given by Gordon too. I'll resort to linear interpolation since I have no libraries available for using splines in the environment I have to work in, but for sure I'll start working on my own library to overcome this absence. Best Regards Sergio Rossi
From: deltaquattro on 19 Feb 2010 09:04 On 17 Feb, 21:17, Arjan <arjan.van.d...(a)rivm.nl> wrote: > Don't extrapolate! This will lead to disasters! Get the interval that > is covered by both functions and limit h to that domain! > Eheh, you're right :) I came to the same conclusion. Wonder why I didn't think of it before! > The Bezier coefficients may have been estimated using a criterion that > will give you f and g with a certain precision, but this does not > guarantee precision of h! Division can lead to asymtots. Hmmmm....you're right. However, if I don't need to guarantee a given precision (for now!), but only that h does not "explode" wildly, then isn't this only really a big issue when g gets "near to" zero? That should not happen in my cases, where g is usually not less than 0.2, and the same for f. BTW, It's possible that in a not-too-far future I'll have to estimate those coefficients (which for now are given to me). Can you point me to algorithms for estimating them, and criterions for checking error, smoothness, and so on? In particular, I'd be interested in criterions which take into account also the errors on the derivative. How do you > expect to catch them? In case you estimated those Bezier coefficients > yourself, possibly because f and g are too time-consuming to calculate > from their definition, isn't it possible to use the original functions > behind f and g just once again, in your construction of a new array of > values for h? ;-) I wished! Unfortunately for now I don't have access to the original definitions of f and g. But once I'll get it, surely I'll do as you say. > > Arjan Thanks, Best Regards deltaquattro
From: Gordon Sande on 23 Feb 2010 09:26
On 2010-02-19 09:42:40 -0400, deltaquattro <deltaquattro(a)gmail.com> said: > On 16 Feb, 18:56, Gordon Sande <g.sa...(a)worldnet.att.net> wrote: >> On 2010-02-16 12:47:26 -0400, deltaquattro <deltaquat...(a)gmail.com> said: >> >>> Hi, >> >> Both numerical analysis and graphics have specialized newsgroups that >> are a better match to what you seem to be asking. > > No. I crossposted to both comp.lang.fortran and sci.math.num-analysis > because I felt that Fortran programmers may be familiar with such > problems, and I was right since all the answers came from > comp.lang.fortran. > >> >>> I have two different functions f(x) and g(x) described as plane Bezier >>> curves, say of fourth degree: >> >>> [f] =[(Pi_x,Pi_y)] >>> [g] =[(Qi_x,Qi_y)] >> >> So f and g are paths in the plane. They will be multivalued and otherwise >> ill behaved as functions y = f(x) or y = g(x). The Pi_x are not monotone >> so this is not a usual way to tabulate a function which one would expect >> to be single valued in any case. Or at least that is what one expects from >> the comment that they are plane Bezier curves. > > They're not multivalued and the Pi_x, Qi_x are monotone. f and g are > functions: they are only described as plane Bezier curves, which means > that their graph (a curve in the plane) has been represented by > interpolation with a plane Bezier curve. I thought that would be clear > from the context, and since the other repliers understood me, that > means that I was at least not too obscure. > >> >>> with i=1..5. I would like to compute some samples of a third curve >>> h(x)=f(x)/g(x). Right now, I'm computing h by calculating f and g at >>> many points, say 21 equispaced values of the parameter t: >> >> What is t (other than arc length along the Bezier curve) and what is >> x as a function of t? Is it single valued? Same for y. > > It's not the arc length, it's just the parameter of the Bernstein > representation: > > f: > x(t)=sum(i=0,...,4)Pi_x*B(t)^n_i > y(t)=sum(i=0,...,4)Pi_y*B(t)^n_i > > g: > x(t)=sum(i=0,...,4)Qi_x*B(t)^n_i > y(t)=sum(i=0,...,4)Qi_y*B(t)^n_i > > where B(t)^n_i are the Bernstein polynomials. In both cases x(t) is a > single valued function of x. > >> it (x_i,f(x_i)) and (x_i,g(x_i)), From your set up it seems y=f(x) or >> y=g(x) so why the change of notation which just confuses the reader >> (and makes the reader wonder if there are other confusions). >> >> One is curious about why the ratio is of interest. That is a question >> about how your problem arises. Perhaps there is an alternate solution > > ? f(x) and g(x)) are two physical quantities which are given, and I > have to calculate the graphs of another quantity which is their ratio. > >> to the actual problem. There are lots of instances of good answers to >> poor questions which end up being poor annswers in substance. Have you >> head about the patient who died when it was an completely successful >> operation for the sugeon! >> >>> t=[0,....19/20,1] -> (x_i,f(x_i)); (y_i,g(y_i)) >> >>> Clearly, x_i and y_i will not in generally coincide, so I interpolate >>> the values of g at the abscissae of f and I compute 20 samples of h as >>> (x_i, f(x_i)/g_interp(x_i)). However, I have two problems: >> >>> 1) since I have the Bezier nodes, I'd like to somewhat interpolate >>> them and then compute h, instead than evaluating f and g on a refined >>> grid and then computing h. It seems to me that I'm wasting cpu time >>> and information. Is there a way to do that? >> >> What is your hourly rate? (Zero if you are a graudate student according >> to the behaviour of the management! :-( ) What is the hourly cost of your >> computer? How many hours of yoour time will save how much computer time? > > I've never been asked such a question when coming to a ng for help. > Can we keep the discussion to the point, please? You open the topic by explaining that you think you are wasting cpu time. All too often there is great expenditure of effort (i.e. the time of a person) in order to save some amount of cpu time. When a university had one computer that cost $1000/hr (and gas was $0.35 a gallon!) it made sense to try to save computer time. Times have changed but the thinking of many stays the same. Many boast about the speed of their programs but few comment on the economic efficiency of solving their problems. Such boasts are often described as coming from folks with too much time on their hands. The hope was that you would do the trivial arithmetic and notice that worrying about cpu cost might not be the highest priority concern. It would appear that I was too subtle and that you missed the point. Early optimization often leads to many other poor qualities of programs. Hard to maintain obscure programs with poor optimization due to poor choice of algorithm. You have done a good job of imitating many of the common indicators of such history based thinking. Much better to have a complete working program based on simple clear programming. Then you can look for timing bottlenecks if the execution time is excessive. Merely polishing code is unlikely to remove bottlenecks. Algorithm improvement is much more likely to be useful. >>> 2) even if I stick to my expensive sampling -> interpolation >>> procedure, it won't always work. The reason is that, because of >>> possible errors in the input, sometimes Again the high cost of the cpu. Is it the major bottleneck in your project? Or just an imitating the habits of others based on old circumstances. >>> P1_x <> Q1_x or P5_x <> Q5_x >> >>> i.e., f and g are not defined exactly on the same interval. So I am >>> not able to interpolate the g samples to the abscissae of the f >>> samples. How can I solve this? Thanks, >> >> If you just had numerical tables giving f and g then one would fit >> some form (low order spline would do well) and then evaluate the rational >> function on whatever set of points you wanted. But you have said enough >> side tracking other things to wonder what it is that you actually want to do. >> > > Thanks for the suggestion. > > Regards > > deltaquattro |