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] y[i] = boxes[i] 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] # static id for first box box1 = modbox[c1] # first box collision = False for c2 in range(c1+1,len(modbox)): # index of second box, incremented by for loop bid2 = modbox[c2] #static id for second box box2 = modbox[c2] # second box count += 1 if ((box1-box2)**2 + (box1-box2)**2) < nearness_sq: # heart of the algorithm collision = True collbox2 = (i for i in boxlist if i == 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 == 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.