mathquadtree

Find the size/level of a node from its position within an quadtree


I have a quadtree. The root node (level 0) is positioned at 0,0 by its centre. It has a width of 16, so its corners are at -8,-8 and 8,8. Since it's a quadtree, the root contains four children, each of which contain four children of their own and so on. The deepest level is level 3 at width 2. Here's a dodgy Paint drawing to better illustrate what I mean:

enter image description here

The large numbers indicate the centre position and width of each node. The small numbers around the sides indicate positions.

Given a valid position, how can I figure out what level or size of node exists at that position? It seems like this should be obvious but I can't get my head around the maths. I see the patterns in the diagram but I can't seem to translate it into code.

For instance, the node at position 1,1 is size 2/level 3. Position 4,6 is invalid because it's between nodes. Position -6,-2 is size 4/level 2.

Additional Notes:


Solution

  • Observe that the coordinate values for the centre of each node are always +/- odd multiples of a power-of-2, the latter being related to the node size:

    Node size | Allowed centre coordinates | Factor
    -----------------------------------------------------
        2     | 1, 3, 5, 7, 9, 11 ...      | 1 = 2/2
    -----------------------------------------------------
        4     | 2, 6, 10, 14, 18, 22 ...   | 2 = 4/2
    -----------------------------------------------------
        8     | 4, 12, 20, 28, 36, 44 ...  | 4 = 8/2
    -----------------------------------------------------
        16    | 8, 24, 40, 56, 72, 88 ...  | 8 = 16/2
        
    

    The root node is a special case since it is always centred on 0,0, but in a larger quad-tree the 16x16 nodes would follow the same pattern.

    Crucially, both X,Y values of the coordinate must share the same power-of-2 factor. This means that the binary representations of their absolute values must have the same number of trailing zeros. For your examples:

    Example | Binary | Zeros | Valid
    ----------------------------------
      X = 1 | 000001 |     0 |   Y
      Y = 1 | 000001 |     0 | S = 2
    ----------------------------------
      X = 4 | 000100 |     2 |   N
      Y = 6 | 000110 |     1 |
    ----------------------------------
      X =-6 | 000110 |     1 |   Y
      Y =-2 | 000010 |     1 | S = 4
    

    Expressions for the desired results: