Fastest way for detecting distance between objects?

Question

I have unknown number of objects in 3D Space, I would like to know what is the fastest way to detect if two objects or many objects have a distance less than a threshold between each others. I think that is an n! problem, but I would like a better way for solving it.

I have tried the following pseudo code, and I need your comment about it.

 for (int y=0; y<blobList.size();y++){
       for (int x =1; x<blobList.size();x++)
       {
           CvPoint *blob_a = new CvPoint();
           CvPoint *blob_b = new CvPoint();
           blob_a->x = blobList[x].second->maxx;
           blob_a->y = blobList[x].second->maxy;
           blob_b->x = blobList[y].second->maxx;
           blob_b->y = blobList[y].second->maxy;

           double dist = distance(blob_a,blob_b);
           cout<< " distance between blob "<<blobList[y].second->label<<"and "<<blobList[x].second->label<<endl;
           cout<<dist<<endl;

           if( dist<ParamMgr.fDistance)
           {

           cout<< " Collision between "<<blobList[y].second->label<<"and "<<blobList[x].second->label<<endl;
           }
           else {
               cout<< " "<<endl;
           }
       }

foreach object { foreach *other* object: take distance } - this is N*N-1 — CapelliC, Feb 21 '12 at 07:59
@Ahmed Saleh - do you have a way to compute the distance between any two given objects? — Adam Matan, Feb 21 '12 at 09:13
@AhmedSaleh This is generally fine. My comments: a. This is much closer to actual code than to pseudocode; You can replace the `blob_=...` section with something like `blob_a, blob_b = max_xy(a), max_x_y(b)`. b. Prefer `i` and `j` as iteration variables. c. If you have avery large number of objects, this iteration might get very slow - consider an RTree implementation for c++, e.g. http://stackoverflow.com/questions/2709339/c-r-tree-implementation-wanted d. — Adam Matan, Feb 21 '12 at 12:22
d. Using only `max` might be erroneous - you need to compare both `min` and `max`. — Adam Matan, Feb 21 '12 at 12:40
@AdamMatan compare between min and max and assign the larger ? — andre_lamothe, Feb 21 '12 at 13:02

Adam Matan · Accepted Answer · 2012-02-21T09:47:48.687

I can think of three solutions, each with a different time\space tradeoff.

n x n array

If you have a small number n of objects and a distance function D(n₁, n₂), you can compute the distances in advance.

Create a 2D n X n array. In array[i, j] store the result of D(n_i, n_j).

Pros:

After the initial calculation, the answer for any two objects is given in O(1).
Simplicity

Cons:

inefficiency for large data sets
Can't easily add new objects on-the-fly

Memoization

Memoize your distance function to remember previous calls.

R-Tree

The standard data structure for storing objects in 2D\3D Objects like Points and Polyhedrons is R-Trees. In short, your objects are grouped into 3D cubes of near-by items. It provides efficient insertion and lookup time of log(n) time, and threshold distance lookup is extremely efficient, especially when the answer is negative.

Quoting the Wikipedia article:

A common real-world usage for an R-tree might be to store ... polygons that typical maps are made of: streets, buildings, outlines of lakes, coastlines, etc. and then find answers quickly to queries such as "Find all museums within 2 km of my current location", "retrieve all road segments within 2 km of my location"

And:

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle.

You have R-Tree implementations in most modern programming languages.

enter image description here

Edward Zhu · Answer 2 · 2012-02-26T08:48:42.520

1

If the 3D space is limited, then we can divide the space into small cubes. The length of each edge is the value threshold. We assume it as d. Then, we just put the objects into the cubes. Pick up the cubes B(x_i, y_j, z_k), which contain the objects. Then we just check the adjacent cubes. At most, for each cube, we will have 27 cubes, including itself. We can ignore the other cubes, since they definitely have distance farther than a threshold.

This solution only works well in the scenario that the nodes are sparse. If all nodes are in the space 3d * 3d * 3d. Then the algorithm will be in the worst case. You can filter no nodes.

edited Feb 26 '12 at 08:48

answered Feb 21 '12 at 08:13

Edward Zhu

166
1
5

There are 26 adjacent cubes. And you will have to check all objects from the currently selected cube as well. Otherwise, good and simple solution – sl0815 Feb 21 '12 at 08:23

score 1 · Answer 3 · edited May 23 '17 at 09:59

In a similar vein to the accepted solution to Looking for a non "brute force" algorithm to remove intersecting areas of a collection of Rects you can sort the objects in one of the x, y or z dimensions and for each object just search forward in the sorted list by the threshold (maybe scaled to account for extra dimensions). This will at least give you all objects that are definitely not close by. For the remaining you can either check their distance and make a decision or a better approach would be to divide the other dimensions into a number of equal sized sections and having classified each object as being in a section if its j-dimension value is in that section. You can more quickly come to a decision as to whether an object is definitely outside the threshold. Overall, for a given object this approach will reduce the number of actual distance calculations to a small number and the problem will scale up efficiently.

Fastest way for detecting distance between objects?

3 Answers3

n x n array

Memoization

R-Tree