How can I convert a QuadTree spatial index (binary index) to Position and Dimension values?
Sorry in advance for overlooking any terminology in this question, but I'm mainly in the business of building a QuadTree that uses binary indexing, like this:
As you can see in the above two illustrations, if each cell is assigned a binary ID (ex: 1010, 1011), then each ODD binary index controls the X offset and each EVEN binary index controls the Y offset.
For example, in the case of a Level 2 (16 cells) 1010 (cell # 10) grid, we can say that it has 1s at the 4th and 2nd indices, so they will do two Y offsets. The first "1 ###" (on the left) indicates the offset of one cell height, then the second "## 1 #" additionally offsets it twice the cell height.
How in:
// If Cell Height = 64pixels
1### = 64 pixels
+ ##1# = 128 pixels
__________________
1#1# = 192 pixels
The same can be applied to the X-axis, instead using odd numbers instead (ex: # 1 # 1).
Now, when I initialize my QuadTree, I started calculating the maximum nodes it can contain if all cells and all depths are used. I calculated this with a sum of 4 to the power of each depth :
_totalNodes = 0;
var t:int=0, tLen:int=_maxLevels;
for (; t<tLen; t++) {
_totalNodes += Math.pow(4, t); //Adds 1, 4, 16, 64, 256, etc...
}
Then I create another loop (iterating from 0 to _totalNodes ) that instantiates the nodes and stores them in a long array. It passes the current iteration integer to Node's constructor and stores it as index .
So far, I could figure out what depth (aka: Level) the Node is stored by calculating its Most Significant Bit index :
public static function MSB( pValue:uint ):int {
var bits:int = 0;
while ( pValue >>= 1) {
bits++;
}
return bits;
}
But now I am stuck trying to figure out how to convert the index from binary to the actual X and Y cell positions. as I said, the sizes of each cell are found. It's just a matter of doing some boolean operations across the entire index (or "bitcode" is the name I call in my code)
If you know of a good example that uses logical operations (binary level) to convert binary index values at X and Y positions, could you please post a link or explanation here?
Thank!
Here's the link where I got this idea from ( note : different programming language):
L. Spiro Engine - http://lspiroengine.com/?p=530
I'm not familiar with the language used in this article, so I can't really follow it and easily convert it to ActionScript 3.0.
source to share
Your task is described by Hannan Samet. This works by first creating a quadrant and then assigning a corresponding overhead to each quad cell. (interleaving bit code).
once you have the code, you assign it to the objects in the square. then you can divide the quad tree. you can search by converting the coordinate to the corresponding questionable code and search the bin in the morton index. Instead of morton (also called z order), you can also use hilbert or gray codes.
source to share