From: "Hermann Kremer" Subject: Re: splines Date: Sun, 9 Jul 2000 01:12:08 +0200 Newsgroups: sci.math Summary: [missing] Laszlo Boros schrieb in Nachricht <271fq24leuzw@forum.mathforum.com>... >The predetermined flight path in a simulation is built using circle >arcs and straigts. Problem: the second derivative at connection point >is not continuous. I want to use a mediate curve (spline?) to connect >them. > >I there a (spline?) curve whith the possibility to define at the >endpoints not only the slope but the radius of curvature too? And how >changes then the curvature radius along the curve? Hello Laszlo, reading your problem I recalled at once the clothoid curve which has the nice property that its curvature (and thus its 2nd derivative) is proportional to the arc length. AFAIK, clothoids are used by road designers to connect a curve smoothly to a straigt road segment. Perhaps the Civil Eng. Dpt. of your university ( tum - thatīs TU Muenchen ? ) can give you some support (Bauingenieure / Strassenbau). As already spamless@nil.nil has pointed out, a 3rd order polynomial spline cannot meet the 2nd derivative constraints; you need at least a 5th order spline. Another approach could be the use of a non-rational spline (NURBS), but I donīt know how smooth the curvature there is. BTW: A better group for your problem than this one would likely be sci.math.num-analysis Regards Hermann -- >Numeric solutions are welcome too... > >I am waiting excitedly for your answer. >Plese, write me if there is a place on the Net with such theory. C >code example would be fantastic! > >Thanks, >Laszlo Boros ============================================================================== From: "Hermann Kremer" Subject: Re: splines Date: Mon, 10 Jul 2000 19:20:54 +0200 Newsgroups: sci.math Laszlo Boros schrieb in Nachricht <271fq24leuzw@forum.mathforum.com>... >The predetermined flight path in a simulation is built using circle >arcs and straigts. Problem: the second derivative at connection point >is not continuous. I want to use a mediate curve (spline?) to connect >them. > >I there a (spline?) curve whith the possibility to define at the >endpoints not only the slope but the radius of curvature too? And how >changes then the curvature radius along the curve? > >Numeric solutions are welcome too... > >I am waiting excitedly for your answer. >Plese, write me if there is a place on the Net with such theory. C >code example would be fantastic! > >Thanks, >Laszlo Boros Hello again Laszlo, can you use my hint to the clothoid (also known as Cornuīs spiral). Imo, if you can manage the computational difficulties with it (itīs defined by transzendental integrals), it should be the ideal solution for your flight simulator -- once again the recommendation to contact the Strassenbau-people at TUM. If you really insist in splines, please send me an e-mail. Some years ago I programmed a 5-th order spline interpolation in C, but without the constraint of curvature = 0 at the connection points to the straight line segments. Since Iīm fairly sure that constraint can be worked in, I will dig out my old code if you let me know. Viele Gruesse Hermann ============================================================================== From: spamless@nil.nil Subject: Re: splines Date: 7 Jul 2000 10:01:19 -0400 Newsgroups: sci.math Laszlo Boros wrote: > I there a (spline?) curve whith the possibility to define at the > endpoints not only the slope but the radius of curvature too? And how > changes then the curvature radius along the curve? Well, not a cubic spline. For a cubic spline passing through the points (x_j,y_j) (j=0 to n: n+1 points) one minimizes INTEGRAL((y")^2*dx) over each interval (x_(j),x_(j+1)) and patches them together to have a function with a continuous curvature. Minimizing the integral is approximately minimizing the energy in a physical spline passing through the points (a flexible stick). Minimizing INTE((y")^2*dx) over each interval leads to a cubic (a_j*x^3+b_j*x^2+c_j*x+d_j) for each interval (ending at x_j:j=1 to n: n cubics) with equations: n equations y_j known at the right endpoint of the cubic over an interval. n equations y_j known at the left endpoint of the cubic over an interval. n-1 equations y' match up at each internal point. n-1 equations y" match up at each internal point. For 4n-2 equations. There are n intervals (cubics) each with 4 coefficients for 4n variables. The "natural" constraint (for the minized energy) is that the curvature be zero at the endpoints (the extra two equations), however if you have different constraints there (the slope given at the endpoints) then use those. One would have to use something more complicated (say, a fifth order polynomial over each interval with 6n coefficients with: n equations y_j known at the left end. n equations y_j known at the right end. n-1 equations y' match up internally. n-1 equations y" match up internally. n-1 equations y"' match up internally. n-1 equations y"" match up internally. Giving 6n-4 equations for 6n variables, leaving room for 4 further specifications, the slopes and curvatures at each endpoint. The equations for the 6n coefficients is just a system of linear equations.) (this would minimize INTEGRAL[(y"')^2*dx] where, inside an interval where there are no constraining points, the Euler-Lagrange equations would be (d/dx)^3[y"']=0 or y"' is a quadratic or y is a fifth order polynomial over each interval) (but why is y"" matching up internally "natural" as an internal constraint? For minimizing INTEGRAL[y"^2] one has to have y" continuous, and so there is a match of y" internally, so too for minimizing INTEGRAL[(y"')^3] one needs y"' to match up internally, but why y""?) ============================================================================== From: spamless@nil.nil Subject: Re: splines Date: 7 Jul 2000 14:45:47 -0400 Newsgroups: sci.math spamless@nil.nil wrote: > One would have to use something more complicated (say, a fifth order > polynomial over each interval with 6n coefficients with: > n equations y_j known at the left end. > n equations y_j known at the right end. > n-1 equations y' match up internally. > n-1 equations y" match up internally. > n-1 equations y"' match up internally. > n-1 equations y"" match up internally. > Giving 6n-4 equations for 6n variables, leaving room for 4 further > specifications, the slopes and curvatures at each endpoint. The equations > for the 6n coefficients is just a system of linear equations.) > (this would minimize INTEGRAL[(y"')^2*dx] where, inside an interval where > there are no constraining points, the Euler-Lagrange equations would be > (d/dx)^3[y"']=0 or y"' is a quadratic or y is a fifth order polynomial > over each interval) ---- > (but why is y"" matching up internally "natural" as > an internal constraint? For minimizing INTEGRAL[y"^2] one has to have > y" continuous, and so there is a match of y" internally, so too for > minimizing INTEGRAL[(y"')^3] one needs y"' to match up internally, but why > y""?) y"" (but NOT y""') comes from looking at the terms one gets by integrating by parts over the subintervals. y""' does not show up since one cannot perturb the value of the function itself (the value is known at the intermediate points) (terms show up involving u'*DELTA[y""] evaluated at interior points x_j where u is a first order perturbation and DELTA is the difference between the values on the right and left of an interior point - the u' values are the same on the left and right, since y' is continuous. As this first order perturbation must vanish, y"" must be continuous. For y""' one would have u*DELTA[y""'] but since the perturbation, u, itself must vanish at interior points as the y values are known there, this term in the first order perturbation automatically vanishes.) ============================================================================== From: spamless@Nil.nil Subject: Re: splines Date: 8 Jul 2000 09:28:27 -0400 Newsgroups: sci.math spamless@nil.nil wrote: > Laszlo Boros wrote: >> I there a (spline?) curve whith the possibility to define at the >> endpoints not only the slope but the radius of curvature too? And how >> changes then the curvature radius along the curve? > Well, not a cubic spline. For a cubic spline passing through the points > (x_j,y_j) (j=0 to n: n+1 points) one minimizes INTEGRAL((y")^2*dx) This is not a "great" method, but "works." The problem? The "energy" one is minimizing is not rotationally invariant. If you rotate the points, obtain a spline and rotate back you get a different spline than what you would have gotten had you not rotated. Splines started as flexible rods which were passed through plotted points and used to draw curves. The curve did not change if you rotated the plotting table. The shape minimizes the internal energy of the bent rod (with the constraint that it passes through the points). One could minimize the integral of K^2*ds (K=curvature, ds=arclength) to get a rotationally invariant result. The curve shape (from the Euler-Lagrange equations) is not so simple as a cubic. Matching things at the fixed points leads to a large (depending on the number of data points) system of *non-linear* equations. For y' not too large, replacing 1+y'^2 by 1 (in the formula for K and ds) results in minimizing the integral of y"^2*dx which leads to cubics and a system of linear equations to match the cubics up over each subinterval. All the methods are just interpolations, not necessarily accurate representations of data between the known data points. You ask what happens to the curvature along the interpolated curve. It is messy since the curve is not based on intrinsic coordinates (curvature, arclength) (if you rotate the data points, get a spline and rotate back, you get something different). There is no real "justification" for using cubic (or fifth-order if you want to fix the slopes and curvature at the end points) splines other than that, for y' not too large (which can change if you rotate the curve) it is "like" minimizing the integral of K^2*ds (for cubic splines) (close to what one would get if one used a "physical" flexible-rod spline). The equations (cubics on subintervals and a system of linear equations to match them up at the data points) are tractable. They look nice :-) You could check formulas for the thin, flexible rods (the internal energy and the curves they assume which are obtained by minimizing this under certain constraints) - but nobody does. All you are doing is interpolating ("guessing" intermediate values).