CODEWITHSUNDEEP
algorithmmathopencv
Andre Ahmed
Andre Ahmed

Reputation: 1891

Fastest way for detecting distance between objects?

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;
           }
       }

Upvotes: 3

Views: 3494

Answers (3)

Edward Zhu
Edward Zhu

Reputation: 166

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.

Upvotes: 1

martino
martino

Reputation: 308

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.

Upvotes: 1

Adam Matan
Adam Matan

Reputation: 136499

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(n1, n2), you can compute the distances in advance.

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

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

Upvotes: 10

Related Questions