Algorithm to calculate trajectories from vector field

Question

I have a two-dimensional vector field, i.e., for each point (x, y) I have a vector (u, v), whereas u and v are functions of x and y.

This vector field canonically defines a set of trajectories, i.e. a set of paths a particle would take if it follows along the vector field. In the following image, the vector field is depicted in red, and there are four trajectories which are partly visible, depicted in dark red:

I need an algorithm which efficiently calculates some trajectories for a given vector field. The trajectories must satisfy some kind of minimum denseness in the plane (for every point in the plane we must have a 'nearby' trajectory), or some other condition to get a reasonable set of trajectories.

I could not find anything useful on Google on this, and Stackexchange doesn't seem to handle the topic either.

Before I start devising such an algorithm by myself: Are there any known algorithms for this problem? What is their name, for which keywords do I have to search?

Answer 1

Obviously, you are dealing with a set of differential equations:

dx/dt = u(x, y)
dy/dt = v(x, y)

There a lot of algorithms, which can actually integrate such equations, but it will depend on the u and v (are they linear or not etc.). Can you provide some more info on this?

In relation to your requirement, is it correctly understood that you want to create multiple trajectories 'close to each other? Or do you mean something else?

EDIT:

I must have been a little confused when I wrote my original post. Obviously, the differential equations are linear, and the actual form of u and v are of less importance.

In fact, integrating these equations are quite simple. If the accuracy is less important, you could do a simple Euler integration - otherwise you might want to look into Runge-Kutta methods (for instance RK4 - fourth order Runge-Kutta).

Both of these are well known, thus I will not go into details here. Do a google search or check wiki:

Euler method
Runge-Kutta methods

Achieving denseness is somewhat more tricky I guess. As your differential equations are linear, slightly displacing the two initial positions will result in similar trajectories. Obviously, you can get the trajectories as similar as the computers precision allows. If you instead want the two trajectories to end in similar points, you can simply define the ending point and do the reverse integration.

Answer 2

This is about solution of differential equations.

In your case f(t) is position of particle in time moment t. f'(t) is velocity of point moving along this trajectory.

So if the vector field defines direction and magnitude of velocity, then the equation is f'(t)=V(f(t)).

To solve such equation you need some starting point. In "good" places where not many trajectories from different directions converge, it's OK to have even middle point and solve the equation in both directions.

So one of possible solutions for ensuring "denseness" is:

1. take random point
2. build trajectory for it
3. find point with maximal distance from existing trajectories
4. if this distance is small enough - we are done
5. build trajectory for this point
6. go to 3

Answer 3

Naive algorithm, that is based on numerical methods (like nilu says):

1. Take starting point as current point
2. Calculate vector based on closest vectors in field and weighted based on distance of current point to them
3. Calculate new point based on current point, calculated vector and some epsilon, that states length of step
4. Repeat 2 and 3 to get list of points of your trajectory

Step 2. would be trickiest. First thing that comes to mind is to use same kind of weighted distance math, that is used in perlin noise. It would probably need some fine-tuning to get results with acceptable error. But you can only do "this much" with low-density field.