I am given several coordinates on a 2D plane. These points represent the centers of circles of a constant specified radius. I've been working on a program that outputs all of the coordinates of the circles that collide. This is simple to do if I simply create a distance matrix and output the points associated with distances less than the radius (proximity_threshold). However, the time complexity for this algorithm is too much.

I've been working on an algorithm that finds a colliding box and takes it out of future distance matrix calculations. However, this gives me false negatives since the distances from other boxes can't be calculated. I know I have to have a recursive algorithm for this, and I know how to implement it, but I need help in doing so. This is what I have so far.

```
#!/usr/bin/env python
from pylab import *
import copy
def get_proximal_boxes(boxes,proximity_threshold):
if proximity_threshold == None: return
if len(boxes) < 2: return
idxs = []
deleter = []
nearness_sq = proximity_threshold**2 # avoid use of sqrt
boxlist = [i for i in enumerate(boxes) # id's each box
modbox = copy.deepcopy(boxlist) # copy of boxlist to be modified
# for purposes of plotting:
x = [i for i in range(len(boxes))]
y = [i for i in range(len(boxes))]
for i in range(0,len(boxes)):
x[i] = boxes[i][0]
y[i] = boxes[i][1]
count = 0
c1 = 0 # index for first box, incremented by while loop
terminator = 10 # any number greater than 1
while terminator > 1:
bid1 = modbox[c1][0] # static id for first box
box1 = modbox[c1][1] # first box
collision = False
for c2 in range(c1+1,len(modbox)): # index of second box, incremented by for loop
bid2 = modbox[c2][0] #static id for second box
box2 = modbox[c2][1] # second box
count += 1
if ((box1[0]-box2[0])**2 + (box1[1]-box2[1])**2) < nearness_sq: # heart of the algorithm
collision = True
collbox2 = (i for i in boxlist if i[0] == bid2).next() # second box is to-be-marked for removal
deleter.append(collbox2) # second box is marked for removal
if idxs.count(bid2) == 0: idxs.append(bid2) # static id of to-be-removed box is stored
if collision:
collbox1 = (i for i in boxlist if i[0] == c1).next() # first box is to-be-marked for removal
deleter.append(collbox1) # first box is marked for removal
if idxs.count(bid1) == 0: idxs.append(bid1) # static id of to-be-removed box is stored
else: c1 += 1 # index for first box increments by 1
for i in deleter:
if i in modbox: modbox.remove(i) # to-be-removed boxes are deleted from modifiable list
terminator = len(modbox) - c1 # calculates operations left
return idxs, count, x, y
def get_test_coords(n=20,maxx=5,maxy=5):
return [[Util.get_frand(0,maxx),Util.get_frand(0,maxy)] for i in xrange(0,n)] # a library is imported for this function, you can create your own random variables if you prefer
def main(argv):
test_coords = get_test_coords()
idxs,count,x,y = get_proximal_boxes(test_coords,.4)
#print "idxs: ", idxs, " | ", len(idxs), " collisions | ", len(idxs)*100./len(x), "% collide |\n\nCount: ", count
print "idxs:", idxs, "| count:", count, "| x:",x,"| y:", y
print "Count", count, "vs", .5*20*21
# plot data
ax = subplot(111,autoscale_on=True,animated=False)
for i in range(0,len(x)):
ax.plot([x[i]], [y[i]],'go')
for i in idxs:
ax.plot([x[i]], [y[i]],'rs')
show()
if __name__ == "__main__":
main(sys.argv)
```

I want to optimize the algorithm even more by identifying each point to a grid of size proximity_threshold and only test points that are in the 8 sorrounding grids. However, I am lost as to where to start with first identifying each coordinate to a grid ID. I would appreciate any help with this.

Thank You!