Non-monotonic spline fitting

Question

I've done a spline interpolation of a 3D path using 2 2D fits. Using the interpolation condition as well as the requirement to be 2 times differentiable I got the required equations to interpolate my 3D path. However I came to realize, that I disregarded the fact, that the paths are not monotonic due to obstacles and therefore the fitted splines can't be calculated.

I can't find anything on spline fitting without monotonous data-sets. Is there a way to adopt to this fact? (I found out, that the points have to satisfy the (Schoenberg-Whitney) conditions, which basically looks like monotonicity to me to be uniquely fit by least squares).

Any suggestions for adoptions or different algorithms? Only thing by now I could find is this: heremite, which requires the derivatives at the endpoints, which is not ideal for my purposes. I would love something as simple as "regular" splines (3rd order polynomials with continuity conditions).

I also found this question, which only states something about hermitian polynomials (which I like to avoid).

In the end this is used for a control algorithm, which needs the curves to be defined implicitly (not parametric). For example y - p(x) = 0. What is not possible for me is: p(t)=y, x(t) where t is the parameter. If the parameter can be eliminated, yielding an implicit representation, it's fine.

Answer 1

You can generate monotonicity for any series of 3D points by simply taking the accumulated distance from point to point as the independent (monotonic) parameter. Think of it as the length of a piecewise linear path p connecting all the points ...

Edit: ... like in (pseudo code):

p[0] = 0;
p[i] = p[i-1] + sqrt((x[i]-x[i-1])^2 + (y[i]-y[i-1])^2 + (z[i]-z[i-1])^2)

Once you have this parameter you can do three spline curve fits for the three dimensions (x, y and z) separately. That way your 3D curve fitting can deal with any conceivable series of points. Using this path p for the spline interpolation will also make it more "physical" as points close together will be treated as such.

For simplicity - especially if your data points are more or less equally spaced - you could simply use the ordinal numbers of each point (like 0, 1, 2, 3, ...) as the independent monotonously increasing parameter.

Answer 2

Since the paths are not monotonic it follows, that no (injective) function can exist, which describes them! This is easy to think of, if a path is considered, where you go forwards, backwards and forwards again. Without a parametric representation (e.g. time) it wouldn't be unique, where the path is. In other words: if y=sin(x), now at which position is the path for y = 0? The infinite solutions are x=k*pi of course, but it is obvious here, that this is not unique.