kd tree for BusArrivalBot

kd-tree.py

#Helper function for the getNearest function
#isOdd should start as true (counting first level as 1)
#curNode starts from root
#searches for nearest stop to query that is not already in the blacklist
def getNearestH(self, curNode, isOdd, queryPoint, champion, blacklist):

    if curNode == None: #base case
        return champion
    else: #get distance of queryPoint to current stop
        stopLocation = (curNode.data["Latitude"], curNode.data["Longitude"])
        curDist = vincenty(queryPoint["Coordinates"], stopLocation).meters
        #print(curNode.data)

    #update champion
    if curDist < champion["Distance"] and self.notPresent(blacklist, curNode.data):
        champion["Distance"] = curDist
        champion["Object"] = curNode.data

    #check which plane to compare the point and traverse roots of current node
    if isOdd: #compare longitude
        #check if hypersphere intersects axis of current node
        borderCoord = (queryPoint["Latitude"], curNode.data["Longitude"])
        borderDist = vincenty(queryPoint["Coordinates"], borderCoord).meters
        if queryPoint["Longitude"] < curNode.data["Longitude"]:
            #go left if queryPoint is left of node
            champion = self.getNearestH(curNode.left, False, queryPoint, champion, blacklist)

            #if hypersphere intersects plane
            if champion["Distance"] > borderDist:
                #go right branch
                champion = self.getNearestH(curNode.right, False, queryPoint, champion, blacklist)
        else:
            #go right
            champion = self.getNearestH(curNode.right, False, queryPoint, champion, blacklist)

            if champion["Distance"] > borderDist:
                #go left branch
                champion = self.getNearestH(curNode.left, False, queryPoint, champion, blacklist)

    else: #compare latitude
        borderCoord = (queryPoint["Longitude"], curNode.data["Latitude"])
        borderDist = vincenty(queryPoint["Coordinates"], borderCoord).meters
        if queryPoint["Latitude"] < curNode.data["Latitude"]:
            #go left
            champion = self.getNearestH(curNode.left, True, queryPoint, champion, blacklist)

            if champion["Distance"] > borderDist:
                #go right branch
                champion = self.getNearestH(curNode.right, True, queryPoint, champion, blacklist)

        else:
            #go right
            champion = self.getNearestH(curNode.right, True, queryPoint, champion, blacklist)

            if champion["Distance"] > borderDist:
                #go left branch
                champion = self.getNearestH(curNode.left, True, queryPoint, champion, blacklist)

    return champion