Quad-tree.py

        def analyze_node(self, node, obj, r):
            #return true if one of the leaf or subleaf is in range of v2
            #return false if the node is out of range
            #it doesn't analyze all the children if it finds one in range it return
            if node.is_leaf() and not node.is_empty():
                #if the node data is in range return true
                if intersect_p_r(node.data.get_position(), obj.position, r) and not id(obj) == node.data.get_id():
                    return True
            elif node.is_split_node():
                for children in node.nodes:
                    if self.analyze_node(children, obj, r):
                        return True
            return False

        def find_split_node(self, node, obj, r):
            #return the parent node with at least one intersecting point
            parent = node.parent
            if parent == None:
                #it's the root
                return node
            if self.analyze_node(parent, obj, r):
                #parent has children in range
                if parent.parent == None:
                    #print "I'm the root"
                    return parent #stop the iteration
                return self.find_split_node(parent.parent, obj, r)
            else:
                return parent #found a node before the root that doesn't have children intersecting the range

        def point_in_range(self, split_node, obj, r, point_list):
            for children in split_node.nodes:
                if children.is_leaf() and not children.is_empty():
                    if intersect_p_r(children.data.get_position(), obj.position, r) and not  obj.position.is_equal(children.data.get_position()):
                        point_list.append(children.data)
                if children.is_split_node():
                    point_list = self.point_in_range(children, obj, r, point_list)
            return point_list

        def range_search(self, obj, r):
            point_list = [] #the objects/point in range list
            tnode = self.find_obj(obj) #find the node that corresponds to the object
            split_node = self.find_split_node(tnode, obj, r) #the node where the parent has at least one intersecting children
            for children in split_node.nodes:
                if children.is_leaf() and not children.is_empty():
                    #check if the node itersect with the children
                    if intersect_p_r(children.data.get_position(), obj.position, r) and not  id(obj) == children.data.get_id():
                        point_list.append(children.data) #append the points contained in the node
                elif children.is_split_node():
                    #else recurse over the childrens
                    point_list = self.point_in_range(children, obj, r, point_list)