Skip to content

in_quadtree

in_quadtree(point, C, W, CH)

Find quadtree cell containing point

Traverses a quadtree in logarithmic time to find the smallest cell (and every other cell) containing a given point in 2D space.

Parameters:

Name Type Description Default
point numpy double array

Query point coordinates

 required
C numpy double array

Matrix of cell centers

 required
W numpy double array

Vector of half cell widths

 required
CH numpy int array

Matrix of child indices (-1 if leaf node)

 required

Returns:

Name Type Description
i int

Index of smallest cell containint P into C,W,CH (-1 means the point is not in the quadtree)
others numpy int array

others vector of integers to all other (non-leaf) cells containing P
See Also

initialize_quadtree.

Notes

Only works for 2D quadtree. 3D functionality is coming soon.

Examples:

# Random points
P = np.random.rand(100,2)
# Get quadtree for random points
C,W,CH,PAR,D,A = gpytoolbox.initialize_quadtree(P,graded=True,max_depth=8)
# Query point
point = np.array([0.5,0.5])
# Find cell containing point
i,others = gpytoolbox.in_quadtree(point,C,W,CH)
Source code in src/gpytoolbox/in_quadtree.py 
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
def in_quadtree(point,C,W,CH):
    """Find quadtree cell containing point

    Traverses a quadtree in logarithmic time to find the smallest cell (and every other cell) containing a given point in 2D space.

    Parameters
    ----------
    point : numpy double array
        Query point coordinates
    C : numpy double array
        Matrix of cell centers
    W : numpy double array
        Vector of half cell widths
    CH : numpy int array
        Matrix of child indices (-1 if leaf node)

    Returns
    -------
    i : int
        Index of smallest cell containint P into C,W,CH (-1 means the point is not in the quadtree)
    others : numpy int array
        others vector of integers to all other (non-leaf) cells containing P

    See Also
    --------
    initialize_quadtree.

    Notes
    -----
    Only works for 2D quadtree. 3D functionality is coming soon.

    Examples
    --------
    ```python
    # Random points
    P = np.random.rand(100,2)
    # Get quadtree for random points
    C,W,CH,PAR,D,A = gpytoolbox.initialize_quadtree(P,graded=True,max_depth=8)
    # Query point
    point = np.array([0.5,0.5])
    # Find cell containing point
    i,others = gpytoolbox.in_quadtree(point,C,W,CH)
    ```
    """

    others = []
    queue = [0]
    i = -1 # by default it's nowhere
    dim = C.shape[1]

    while len(queue)>0:
        # Pop from queue
        q = queue.pop(0)
        # Check if point is inside this cell
        if is_in_quad(point[None,:],C[q,:],W[q]):
            # If inside this cell, then add to otthers
            others.append(q)
            # Is it child?
            is_child = (CH[q,1]==-1)
            if is_child:
                # If it is, then we're done
                i = q
                break
            else:
                # If not, add children to queue
                queue.append(CH[q,0])
                queue.append(CH[q,1])
                queue.append(CH[q,2])
                queue.append(CH[q,3])
                if dim==3:
                    queue.append(CH[q,4])
                    queue.append(CH[q,5])
                    queue.append(CH[q,6])
                    queue.append(CH[q,7])
    return i, others