I'm trying to develop a fast algorithm to perform 2D interpolation between two parallel lines. Along the way, I found an interesting problem and have been wrestling with it for longer than I should.
Definitions
Let's call the two parallel lines Line A and Line B. For simplicity, let them each be parallel to the $x$-axis with $y$-values of $y_A$ and $y_B$, where $y_A<y_B$.
Line A has $N_A>1$ points sorted in order of ascending $x_{A,i}$: $$(x_{A,1},y_A), \; (x_{A,2},y_A), \; (x_{A,3},y_A), \; \dots, \; (x_{A,N_A},y_A)$$
In similar fashion, Line B has $N_B>1$ points sorted in order of ascending $x_{B,i}$: $$(x_{B,1},y_B), \; (x_{B,2},y_B), \; (x_{B,3},y_B), \; \dots, \; (x_{B,N_B},y_B)$$
In general, the lines have some overlap along the $x$-axis.
Let there be an unknown (but smooth) function $f(x,y)$ which is sampled at these points. We can denote these known function values along Line A at point $(x_{A,i},y_A)$ as $f_{A,i} \equiv f(x_{A,i},y_A)$, and along Line B at point $(x_{B,i},y_B)$ as $f_{B,i} \equiv f(x_{B,i},y_B)$.
Problem Statement
Given these points, I know I could in principle calculate a Delaunay triangulation in order to calculate the interpolated value $f_Q$ at a query point $(x_Q,y_Q)$ in between the lines, where $f_Q$ is an estimation of the unknown function $f(x,y)$ at the query point: $f_Q \approx f(x_Q,y_Q)$.
Creating a whole triangulation for the entire set of points seems like overkill for a single point, however. I suspect there's a more efficient way to do this, e.g. by figuring out which x-coordinates are above/below $x_Q$ and/or how far away nearby points are.
How can I figure out which triangle (out of the entire Delaunay triangulation) the query point is in without actually computing the entire Delaunay triangulation for all points on both lines?
My work thus far:
Given a query point, I can figure out a set of three points from both lines that contains the point, but the triangle is not unique for all points inside it. In other words, if I were to choose another point in that triangle, the same algorithm I currently use might give me a different triangle to interpolate on. For a mesh of query points, this makes the mesh of interpolated values discontinuous. I'm thinking of the Delaunay triangulation because it is unique, but don't want to compute the entire scheme for every query point.
(NOTE: I'd be interested in comments about an alternate way to do interpolation between these two lines, but the answer should be focused on how to "shortcut" the Delaunay triangulation algorithm for two parallel lines.)