Collision Detection

[atqamar]

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!

[woooee]

This may or may not help. First you want to find out if 2 circles do intersect. You can find the distance from the center of circle A to the center of circle B by constructing a right triangle. If (radius_A + radius_B) is greater than the distance you have an intersection.

A line perpendicular to the line that connects the two centers will intersect the two points where the circles intersect, so you can use the divide by two method. Start by drawing a line from the center of one circle to the edge (one radius) on a point that you know is outside of the intersecting parts (or try in increments of 90 degrees). The distance from that point to the center of the second circle should be the radius of the second circle if you are at the intersecting point. You now divide the angle in half that was used to draw the line to the edge of the first circle and see if it is inside or outside the intersecting portion (distance to the center of the second circle is greater or less than the radius). You then know which half to use to divide in half again. You can look at one million numbers in 21 passes using the divide by two method.

This link has a good picture of what I was clumsy in describing. You want to find BA and BD. It also says you can use the law of cosines but that is beyond me. http://mathcentral.uregina.ca/QQ/database/QQ.09.07/h/muhammad1.html

[atqamar]

woooee, Thanks for the quick response.

However, I think the method you are using complicates the process.

Let me explain what I am trying to do:

I have a list of 2D coordinates: [A,B,C,D,E,...] These coordinates represent the center of circles of a constant radius. I would like to test if these circles overlap/intersect/collide. It is simple to do if you take the distance between each point and test whether it is less than the proximity_threshold (=2r). However, this has a large time complexity because in this case you would be testing AB, AC, AD, AE, BC, BD, BE, CD, CE, DE ... The number of tests can be reduced if we find that a certain coordinate is too close. Let's say B, C, and D all collide with A. Now, we only should test collision for A and E and stop there.

I know there is a recursive way to do this, but I am having difficulty in implementing it.

And my second question was this: How can Python be used to categorize each point to a grid in 2D space, so I only test points that are in nearby grids?

Thanks !