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:
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:
S
) = 2 ^ (Zeros + 1)