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

Question

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:

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:

• Positions are addresses. They are exact and not worldspace, which is why it's possible to have an invalid address.
• In practice the root node size could be as large as 4096, or even larger.

Answer 1

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:

• Size (S) = 2 ^ (Zeros + 1)
• Level = [Maximum Level] - Zeros