How to: Using Sweep and Prune Algorithm to Check Distances Between Points

I'm working on a project that requires the distances between points to be checked. If two points are close enough, do something...you get the idea. Right now I'm do the naively looping through the points exponentially.

Code (csharp):

1.  
2. for(all the points)
3.      for(all the points)
4.           check distance
5.  

The calculation time gets to be ridiculous at about 80 points! I know people use the sweep and prune method to check a bunch of objects and see where they are in relation to other objects. Other people's implementations have been a bit over my head and I don't know if they are directly relevant to my needs.
Here's the chunk of code that id doing the nasty amount of computations:

Code (csharp):

1.  
2. //The iPoint and jPoint variables, just like most of the other in this method, are declared outside of the loop rather than
3. // recreating it each time. They're main purpose is to make the code slightly more readable and iPoint. However, assigning iPoint
4. // outside of the inner loop is slightly faster than the alternative; getting point[i] everytime the inner llop is run.
5. Vector3 iPoint;
6. Vector3 jPoint;
7.  
8. // Each loop increments through every index in the list of points. We'll use this to look at every possible connection
9. for(int i = 0; i < pointCount; i++)
10. {
11.     // iPoint is set in the outer loop to optimize the loop slightly.
12.     iPoint = points[i];
13.    
14.     // Now we loop through the list of points again, essentially looking at every possible connection for the current point
15.     // index that the outer loop is on.
16.     for(int j = 0; j < pointCount; j++)
17.     {
18.         // If we have more lines than the mx number of lines we can stop all of our calculations.
19.         if(lines.Count > maxLines - 1)
20.             return;
21.         // If the current point has to many connections we'll break out of this loop, returning control to the outer loop
22.         // and continuing on to the next point.
23.         if(currentLinesFromPoint > maxPerPointConnections)
24.             break;
25.        
26.         // We'll s set jPoint. Because were in the nested loop, using jPoint isn't any faster, but it's consistent and
27.         // more human-readable.
28.         jPoint = points[j];
29.        
30.         // If the two points we are comparing are the same we shouldn't need to make any connections.
31.         if(i == j || iPoint == jPoint)
32.             break;
33.        
34.         // If we've gotten to this point we can actually check if the two points are close enough to create a line.
35.         // If the distance between the two points is less than the actualMaxDistance (which is the scaled maxDistance)
36.         // we can create a line.
37.         if(Vector3.Distance(iPoint, jPoint) < actualMaxDistance)
38.         {
39.             // AddLine takes a start/end point, start/end point indices in the points list, the desired line width, and the mesh
40.             // to add the line to. AddLine creates the line and then returns a new Line object. We store the Line in a list of lines
41.             // for further use. If you want to know more about the list of lines just go to the top of the script and fine the summary for it.
42.             lines.Add(VexusUtils.AddLine(iPoint, jPoint, i, j, lineWidth, lineMesh));
43.            
44.             // If we've gotten to this point we know that i and j have been used to create a line so we'll add those indices to usedPointIndices.
45.             usedPointIndices.Add(i);
46.             usedPointIndices.Add(j);
47.            
48.             // We've created a line so we can increment currentLinesFromPoint.
49.             currentLinesFromPoint++;
50.         }
51.     }
52.     // At the end of the inner loop we've just finished creating all the desired lines from a point and are just about to move to the next point,
53.     // so we'll set currentLinesFromPoint equal to zero so that the next point adds to its line count from zero.
54.     currentLinesFromPoint = 0;
55. }
56.  

 

I assume you're doing this double for loop inside update? If you're going to write double for loops like that, you have to make sure either the data set is small, or the calculation doesn't happen often. (there are some very clever ways around this, but they're unique to the situation)

What I recommend for you is to do that check only once when the points are created. After that, whenever you add or move a point, check only that point against the entire list of points. This removes the exponential growth of the computation time, and now you don't even have to check every frame.


Hope this helps!

 

What exactly is the use case here? What is the behaviour of these points?

 

I'm drawing lines between them. In the simplest sense, if two points are close enough, I draw a line between them.

 

Thanks, I have a pretty robust system and you can turn off the calculations so that they update once the connections once. However, I want the connections to update every frame and all the points are moving so I can't only update a few. I was thinking about threading the calculations so that each thread can take a chunk of the loops, but Unity is very limiting when it comes to creating threads. Check out the sweep and prune algorithm and you might be able to see what I'm trying to accomplish. It effectively removes any exponential calculations (for the most part) from comparing values in a list.

 

First off, it's quadratic, not exponential (done being pedantic )

You should look up using octrees, and see if they'd be appropriate here. I've used them for collision detection and it's pretty much the same thing. Basically, the core idea is that you partition your space into a 3D grid. So you have this array of grid cells, and each grid cell holds a collection of objects inside of it. If you choose your grid cell properly, then you'll only need to check distances against objects in neighboring cells.

One other quick optimization is that, if i is close to j, then j is also close to i, so you don't have to do that computation twice.

I don't have time to write up a sample, but hopefully looking up octree collision detection will put you on the right course. You might still end up paying O(n^2) to draw the lines, but the detection should be much faster, and it may be much faster in the average case.

 

Thanks, I'll look into octrees and optimize my i and j calculations.

 

The physics system already handles octtrees and distance quite well. You could consider leveraging the existing system. Use a ridgidbody with a trigger attached.

A custom system might be faster. But it will certainly take longer to code.

 

I'd like to make my own system, as I'll have more control. I also want to avoid doing any "hacky" code.