Intersection-detection algorithm

Question

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.

Answer 1

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.

To actually rework your code:

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.

Your code reworked:

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