CODEWITHSUNDEEP
c++algorithmscientific-computing
Yotam
Yotam

Reputation: 10675

Is there an efficient way to determine a distance?

This question is more about the algorithm and the right use of function rather than the actual code.

In my code, I'm using map to simulate boxes. The maps elements are composed of vector<int> as keys and set<shared_ptr<foo> > as values.

I'm doing a nested loop to go over all the boxes:

mit1 = boxes.begin(); //mit1 is an appropriate iterator
int edge = 10;//represnd periodic boundary conditions
while (mit1 != boxes.end()){
  vector<t> = mit1->first;
  mit2 = mit1++;
  while (mit2 != boxes.end()){
    vector<int> u = (mit2++)->first;
    bool good = true;
    for (int i = 0; i < 3 && good; i++){
      u[i] = (int)fabs(u[i] - t[i]);
      good = u[i] == 0 || u[i] == 1 || u[i] == edge;
    }
    if (!good) continue;
  }
}

My concern is with the whole nested loop as well as the for loop. Would you consider it to be more efficient to have a function to calculate all the neighboring boxes? Do you know of any better way to do the for loop test?

Upvotes: 3

Views: 405

Answers (3)

David Hammen
David Hammen

Reputation: 33106

This is a simplified version of the general collision / mindist problem. Those problems get particularly nasty when you have a bunch of objects, each described by many polygonal faces. There isn't a one size fits all solution to these problems. There are lots of heuristics that help attack this problem. A few of them:

  • Use bounding spheres as well as bounding boxes. The distance between a pair of spheres is a lot easier to calculate than the distance between a pair of boxes, and the distance between a pair of bounding spheres is never more than the distance between a pair of bounding boxes. This lets you rule out lots and lots of calculations fairly quickly.

  • Use a hierarchy of objects. If objects A, B, C, and D are always in close proximity to one another it is oftentimes useful to create a metaobject that contains A, B, C, and D. If you can rule out considering this metaobject as a candidate you have just ruled out consider any of the objects within as a candidate.

  • If the objects are moving slowly, the nearest neighbor at the next step is oftentimes the nearest neighbor at the current step. Start with this as the first guess, then search other nearby objects, then go further abroad. Eventually (typically sooner than later) you will ruled out all the remaining objects.

Upvotes: 1

thiton
thiton

Reputation: 36049

Same advice as with every collision detection: Use some algorithm or data structure that allows you to pre-filter candidates for your loop by their spatial distance, and allows to do this pre-filtering in O(n). A quad tree comes to mind, or a coarse-grained spatial map.

Edit: To make the whole idea a little bit clearer, consider the following algorithm: You have N particles in a 3D space and want to find out which particles are closer than a distance D to each other. You build a 3D array, with each bin representing a cubic volume of your target space, and each volume must be at least of size D. To find all particles that might be closer than D to a given particle X, you determine the array cell Ax in which X is currently and select all particles from the Ax and all surrounding cells. You only need to check this small subset for collisions.

When using M array cells, the average-case computational complexity for the whole distance check is now O(N*N/M) instead of O(N^2), however at the cost of O(M^2) space.

If your target space is unbounded, use a quad tree (2D) or an oct tree (3D).

Upvotes: 4

Nir
Nir

Reputation: 33

Depends on what your program is doing...

But it's possible to calculate the distance when a box moves. Then it optimizes some if not all boxes are moving.

Upvotes: 0

Related Questions