retrieveTree.py

def retrieveTree(self, qp, level=0, arr):
    """
    INPUT
    qp : query point of (x, y)
    level : initial level, default set to 0
    arr : dataset containing vertices and its list region

    OUTPUT
    dictionary of {
        'nearest': (int, int),
            --> nearest point to query point (based on kd tree indexing)
        'depth': int, 
            --> depth of search
        'region': int,
            --> the result, region of the query point at
    }
    """

    # BASIS START
    ### memeriksa listRegion di curentNode
    ### jika qp terdapat pada salah satu region, return
    from inside_Polygon import inside_Polygon
    listRegion = self.koordinat[2]
    region = inside_Polygon(qp, listRegion, arr)
    if region:
        return {
            'nearest': self.koordinat,  # nearest point
            'depth': level,             # depth of search
            'region': region            # region of the query point at
        }

    # RECURSIVE PREPARATION START
    ### retrieve child using KDTree indexing
    if level % 2:
        # ganjil
        if qp[1] < self.koordinat[1] and (hasattr(self, 'left')):
            childNode = self.left
        elif qp[1] > self.koordinat[1] and (hasattr(self, 'right')):
            childNode = self.right
    else:
        # genap
        if qp[0] < self.koordinat[0] and (hasattr(self, 'left')):
            childNode = self.left
        elif qp[0] > self.koordinat[0] and (hasattr(self, 'right')):
            childNode = self.right

    level += 1

    # RECURSIVE START
    ### try to get the result from its child
    return childNode.retrieveTree(qp, level, arr)