# Estimating line paths in vector fields.

Assume I have a vector field sampled in discrete points. For simplicity let us assume it is sampled regularly on a Cartesian grid. I want to estimate flow lines through various points in this vector field. I.e. trajectories "along" the vector field. Say that I also know at least one point I want the flow line to pass through. How can one do this?

One approach which seems nice to me is to approximate with a polynomial, as some kind of a Taylor polynomial. However I suppose this would be a $\mathbb{R} \rightarrow \mathbb{R}^2$ polynomial as it should be parameterizable by just one real value. So trying to estimate $P_x(t),P_y(t)$ where $P_x$ and $P_y$ are polynomials of some degree. It seems like a reasonable approach to me, but I'm very curious of how you guys would approach the problem.

The problem consists of two:

• Trace line path $\mathbf r(s)$ with field $\mathbf v$ given at any point $\mathbf r$, i.e. solve $$\frac{d\mathbf r(s)}{ds} = \mathbf v(\mathbf r(s))\\ \mathbf r(0) = \mathbf a$$
• Given $\mathbf v(\mathbf r)$ only at some points $\mathbf p_i$ reconstruct $\mathbf v$ at an arbitrary point $\mathbf r$.

The first problem can be solved using any suitable ODE integrator, for example, Runge-Kutta one. The simplest Runge-Kutta method is Euler's method: $$\frac{\mathbf r_{n+1} - \mathbf r_n}{\Delta s} = \mathbf v(\mathbf r_n)\\ \mathbf r_0 = \mathbf a$$ This method needs to compute $\mathbf v(\mathbf r_n)$, but the field might not be known there, so we arrive at the next problem: given $\mathbf v(\mathbf p_i) = \mathbf v_i$ compute $\mathbf v(\mathbf r_n)$. This problem can be solved using any type of multivariable interpolation. One of the simplest methods is the bilinear interpolation. Assume that $\mathbf v$ is given on a Cartesian grid: $$\mathbf v(x_i, y_j) = \mathbf v_{ij}$$ and $\mathbf r_n = (\xi_n, \eta_n)$ belongs to $(i,j)$ cell: $$x_i \leq \xi_n < x_{i+1}\\ y_j \leq \eta_n < y_{j+1}$$ Then $\mathbf v(\mathbf r_n)$ can be approximated as $$\mathbf v(\mathbf r_n) \approx (1-u)(1-w)\mathbf v_{i,j} + u(1-w)\mathbf v_{i+1,j}+ (1-u)w\mathbf v_{i,j+1}+ uw\mathbf v_{i+1,j+1}$$ where $$u = \frac{\xi_n - x_i}{x_{i+1} - x_i}\\ w = \frac{\eta_n - y_j}{y_{j+1} - y_j}\\$$

• Nice! I think you explain the multilinear interpolation algorithm much nicer (in mathematical notation) than I did in answering someone else's interpolation question. I'm going to link that answer back to yours; I hope that's OK. – David K Jul 16 '15 at 21:39

I suppose if you know the flow line through a given point, you can use some variable $t$ to parameterize the flow line, find the vectors at a few values of $t$, and use these to produce polynomial approximations $P_x(t)$ and $P_y(t)$. But that's "if you know the flow line ... "! This is not a procedure to find the flow line.

What I have actually done when confronted with a problem like this myself is to write a multi-dimensional interpolation function that can estimate the components of your vector field (or magnitude and direction, if you prefer) at any point in your coordinate space, not just at the sample points.

I've done this with linear interpolation within a multi-dimensional grid, similarly to the method I described in this answer to another question. I suppose it might be possible to do some higher-order interpolation (second-degree polynomials, splines, or something of that sort) but I have not tried it.

Equipped with a suitable interpolation function to estimate the vector field at any point, and a given point (the point you want the flow line to pass through), I then use some form of Runge-Kutta to compute the flow line forward and/or backward from the given point. Basically, this is a numeric solution of a differential equation with one boundary point.