I want to find a curve passing through (or near) $n$ points in the plane. The catch is that the curve need not be a function. That is, a vertical line might pass through the curve in more than one place. I want to treat the $x$ and $y$ coordinates identically.
So, I have a set of points, $(x_1, y_1), …, (x_n, y_n)$ where it is NOT necessarily the case that $x_1 < x_2 < … < x_n$ as is the usual condition for a spline, but I'd like to use a spline-like approximation.
I'm sure this must be a problem that has been thoroughly addressed in the literature, but I can't figure out what to search for. If someone could at least tell me some keywords to search for, I would appreciate it.
Edit: After doing some more thinking and hunting around, I believe the key is going to be to use separate splines to represent the $x$ and $y$ coordinates in terms of some other parameter, $t$, i.e., as a set of parametric equations. So, for example, if I had four points, I could represent $x$ and $y$ as cubic polynomials:
$x = at^3 + bt^2 + ct + d$ and $y = et^3 + ft^2 + gt + h$. Since $t$ is an arbitrary parameter, I could let it take on integer values, e.g., $t = 0,1,2,3$ in order to make solving the system easier.
The problem is that $t$ isn't really a natural parameter. I would prefer something like arc length so that I could calculate and presumably minimize the bending energy. Somehow, I will have to incorporate that into my calculation at a later stage.
Darrell
Best Answer
Your thinking is correct -- you need to use a parametric curve (either a spline or a single polynomial) that gives $x$ and $y$ as functions of some parameter $t$. To compute the curve, you must first assign a parameter value $t_i$ to each point $P_i$. As you say, these parameter values are entirely fabricated -- they are not an intrinsic part of the original interpolation problem. Furthermore, different choices for these parameter values will produce significantly different curves. The usual approach is to choose them so that $t_{i+1}-t_i$ is equal to the chord-length between the points $P_i$ and $P_{i+1}$.
Using arclength seems like the natural approach, as you say, but this doesn't work because you don't know the arclengths until you've constructed the curve -- a chicken-and-egg problem.
There's a bit more info in this answer.
A good reference is this web site.