Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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:

trajectories

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?

share|improve this question
    
For an AI project utilizing potential fields, i found this article useful: Potential Fields Tutorial by Michael A. Goodrich. You might as well?. –  jolt Sep 8 '12 at 15:29
2  
I think that this question would be better suited for StackOverflow. You mention that "Stackexchange" doesn't seem to handle the topic, but quoting the StackOverflow FAQ, "We feel the best Stack Overflow questions have a bit of source code in them, but if your question generally covers … a software algorithm … then you’re in the right place to ask your question!" Either way, I hope you find what you need. –  David Kaczynski Sep 8 '12 at 15:43
1  
I'd use mathematica's StreamPlot function for reference: reference.wolfram.com/mathematica/ref/StreamPlot.html Note that streamlines begin/end when it gets too dense. Also, look at the options for the command. There's even one that specifies the minimum distance between lines. It should give you some ideas for how to implement it. –  NeuroFuzzy Sep 10 '12 at 4:02
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
Yes I need multiple trajectories close to each other (that's what I meant with 'denseness'). And no, u and v are not linear. I don't have any analytical definition for u and v, they are calculated numerically. –  cheeesus Sep 9 '12 at 8:55
    
Thank you, RK4 seems to be the way to go. Strict denseness is not so important, I think I'll go with something heuristic, like marking cells as 'visited' when a trajectory crosses them, and then starting new trajectories on 'non-visited' cells. –  cheeesus Sep 10 '12 at 8:35
add comment

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
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.