# Intersection-detection algorithm

This is an intersection-detection algorithm I developed as an alternative method to the one developed for my coursework. I won't post some of the other functions as they are used in the coursework too, feel free to ask if their names aren't self explanatory. This function simply returns whether 2 bcw objects are intersecting. bcw objects are either boxes or circles. What I'd like is any comments on my algorithm/coding style to help make me a better programmer.

def bcw_do_collide_i(obj_A,obj_B,tracer=None, accuracy = 30):
""" Check whether Box-Circle World objects obj_A
and obj_B collode. If so, return True,
otherwise return False.
"""
# items to be checked
comp1 = [obj_A]
comp2 = [obj_B]

# does a component circumcircle collide, True = collides
truth1 = [False]
truth2 = [False]

# Depth used to limit iterations to accuracy
depth = 0

while len(comp1)!=0 and depth<accuracy:
# Find any non colliding components
for c1,t1 in zip(comp1,range(len(truth1))):
circum_1 = bcw_circumcircle(c1)
for c2,t2 in zip(comp2,range(len(truth2))):
circum_2 = bcw_circumcircle(c2)
if tracer <> None:
tracer([c1,c2,circum_1,circum_2], ["k--","b--","r--","r--"])
if bcw_do_circles_overlap(circum_1,circum_2) == True:
truth1[t1] = True
truth2[t2] = True
# Check for colliding components
in_1 = bcw_incircle(c1)
in_2 = bcw_incircle(c2)
if tracer <> None:
tracer([c1,c2,in_1,in_2],
["g--","b--","r--","r--"])
if bcw_do_circles_overlap(in_1,in_2): return True

# Subdivide all components whose outers collide
sub = []
for c1,t1 in zip(comp1,truth1):
if t1:
sub+=bcw_components(c1)

comp1 = sub[::]
truth1 = [False for i in comp1]

sub =[]
for c2,t2 in zip(comp2,truth2):
if t2:
sub+=bcw_components(c2)

comp2 = sub[::]
truth2 = [False for i in comp1]
depth+=1

return False


I was tempted by using the bcw objects as dictionary keys but they had to be mutable.

A few quick stylistic things:

1. Don't use <>, its considered an older style use != instead
2. When comparing against None, use "x is None" not "x <> None" or "x != None" This is because there is only one None object so its more correct to compare object identity
3. Don't use == True or == False. There are some corner cases that won't do what you expect. They clutter your code and make it look like you don't know what you are doing.
4. Your variables do not provide much hints about what they are doing. For example you have variables named truth. Given that we already knew there were holding booleans thats not very useful.

1. You set values in a truth list, then use those values to decide whether or not to take an action. Flags clutter code. Rather then setting those flags, why don't we maintain a list. By adding a remaining_Comp1 and remaining_comp2 list I push elements in there instead of setting Truth values in my list. This completely eliminates the neccesity of keeping the truth lists and eliminates a lot of the code.

2. You have two for loops which iterate over all possible combinations of elements from your two lists. By using itertools.product, we can make this simpler

3. You check that comp1 is not empty, but not comp2. This looks like an oversight.

4. You are keeping track of depth to make sure you don't go into too much detail. But you've basically reimplemented a for loop. I'd move depth into a for loop and simply bail out with a break statement if comp1 or comp2 is empty.

5. Rather then checking whether trace is None, I recommend using a NullTracer which simply does nothing when it is called.

def bcw_do_collide_i(obj_A,obj_B,tracer=None, accuracy = 30):
""" Check whether Box-Circle World objects obj_A
and obj_B collode. If so, return True,
otherwise return False.
"""
if tracer is None:
tracer = NullTracer()

# items to be checked
comp1 = [obj_A]
comp2 = [obj_B]

for depth in range(accuracy):
if not comp1 or not comp2:
return False

remaining_comp1 = []
remaining_comp2 = []
# Find any non colliding components
for c1, c2 in itertools.product(comp1, comp2):
circum_1 = bcw_circumcircle(c1)
circum_2 = bcw_circumcircle(c2)
tracer([c1,c2,circum_1,circum_2], ["k--","b--","r--","r--"])
if bcw_do_circles_overlap(circum_1,circum_2):
remaining_comp1.append(c1)
remaining_comp2.append(c2)
# Check for colliding components
in_1 = bcw_incircle(c1)
in_2 = bcw_incircle(c2)
tracer([c1,c2,in_1,in_2],
["g--","b--","r--","r--"])
if bcw_do_circles_overlap(in_1,in_2): return True

# Subdivide all components whose outers collide
def expand_components(components):
result = []
for c1 in remaining_comp1:
result += bcw_components(components)
return result

comp1 = expand_components(remaining_comp1)
comp2 = expand_components(remaining_comp2)

return False

• Neat :) exactly the kind of advice I was looking for. I'd never even come across itertools before. Thanks.
– user3269
Apr 12, 2011 at 21:13
• I usually do the x is None and x is not None (this prevents nasty bugs when bool(x) is False). Actually you could do that for numbers as well (e.g. x is 1). The semantics is the same. Would you do such a thing? Feb 11, 2014 at 22:16
• @Dacav, actually it is not guaranteed to work for numbers. In current implementations of Python it'll work for small numbers, but not big ones. See for example: 123456789 + 1 is 123456789 + 1 It's False. Feb 11, 2014 at 23:33