CODEWITHSUNDEEP
algorithminterpolation
chrislacorunna
chrislacorunna

Reputation: 49

3-dimensional interpolation of a line

I have a problem, that I need to do a spline - find a function that will smoothly interpolate through set of 3D Points (y,x,z). Lets say, there is a set of 20 points, each being in R3, so:

P1(10, 10, 10)
P2(11, 12, 14)
P3(12, 17, 11)
P4(13, 14, 20)
...
P20(29, 32, 43)

I want to draw a smooth line that contains these points and find new points, that lay on it with given y value (e.g P21(10.5, x, z)). The problem is pretty obvious for me in 2D, as I can use for example Lagrange interpolation. But cannot really find a solution for 3D line. My first guess would be to do separate Lagrange interpolation for each surface so:

//Lagrange for y, x surface
x=Lx(y)
//Lagrange for y, z surface
z=Lz(y)
//Finding point having y given
Pa(10, Lx(10), Lz(10))

Would that be suitable? I would greatly appreciate any solution for finding a interpolation function in 3D. Any solution in greater dimension would also be helpful for me.

Thanks for your time.

Upvotes: 0

Views: 977

Answers (1)

Iddo Hanniel
Iddo Hanniel

Reputation: 2056

When you say a line I assume you mean a curve (not necessarily a straight line). From the reference in the question to Lagrange interpolation I understand that for your needs a polynomial interpolation is sufficient (even though it may lead to Runge's phenomenon).

A convenient representation for a 3D curve is in parametric form (see for example here) as a tuple (X(s), Y(s), Z(s)) where s is some parameter and each coordinate is a function of s (a polynomial function in your case). Given a parameter si for each of you input points, the curve fitting problem is reduced to the three 2D problems of fitting (si, Xi), (si, Yi), and (si, Zi) separately.

For this to work, however, you need a suitable parameterization si on the input points. In the question you suggest that Yi can serve as such a parameterization. If Yi is indeed a suitable parameterization, then you're in luck and your job is done. You have the functions X(y), Z(y) (Lx(y) and Lz(y) in your question) and can evaluate them at any y-value.

However, in many cases, y is not a suitable parameterization for 3D. In particular, if the (Yi, Xi)-values or (Yi, Zi)-values are not monotone in Yi then it cannot serve as a parameterization.

Since you have an ordering of the points, you can use a uniform parameterization (s0=0, s1=1,... etc.), which is sure to be monotone. A preferable method that is common in spline fitting is the chord-length parameterization. Here the parameterization is defined by the accumulated length of the distances between the ordered points (s0=0, s1=|p1-p0|, s2 = s1+|p2-p1|... etc.). This parameterization will probably give you a nicer fit. These parameterizations extend to higher dimensional curves as well.

The general difficulty in parametric curves is that while they enable you to sample points densely along the curve, finding a point on the curve that corresponds to a given y0 value requires an inverse problem. In your case it requires to find the root(s) of Y(s)=y0 and then plug the root s into X(s) and Z(s). However, this cannot be avoided since for example there can be more than one point corresponding to a given y-value. You can use root-finding methods such as the bisection method or Newton-Raphson to solve the problem.

As a last note you may prefer to use B-spline interpolation (i.e., piecewise polynomial), which has some preferable properties over polynomial interpolation of high degree (see here or any B-spline text book such as "The NURBs Book"). Python's scipy library also has functions for spline fitting (see this SO answer for example).

Upvotes: 3

Related Questions