Hello Everyone,
I am hoping someone might be able to help me with setting up the structure of a quadtree. Basically, I’ve designed the tree to have points (x,y) and dimensions(width,height). Each node has 4 childs, each with a 4 dimension array (x,y,w,h). I can use the points to determine where objects fall into which node.
I’ve setup the underlying details, but what is making my head implode is how to set up the structure such that it is easy to both test early nodes as well as make it easy to tell the location of objects using all their nodes.
I originally thought of using some sort of array/class combo - where you begin with an array that stores your 4 beginning points and each point essentially is a node class (x,y,w,h) which also contains the child arrays, which each have a node class, etc.
This all seems fine, expect when trying to determine how to call a test to a leaf. I’d have to call the initial array’s parent’s child’s child’s child’s … value. XML comes to mind, but I am uncertain if there is a way to combine the flash xml functions with this structure?
The second thought was a large array (ie. [[[[[[ ]]]]]]); which would allow finite calls: ie. [0][1][1][3][2][0] would call node0’s child1’s child1’s child3’s child2’s first leaf. This also can be used to assign a specific code to each object in the data structure. (Ie. the above code is 011320) But I have a problem creating a loop that handles setting up points for each array, unless the final value is set as an array of all the points taken to achieve the final leafs point (yea - that sounds like a lot of overhead).
The third thought was to go strictly one class - a node class that contains (x,y,w,h) for each of its children. A loop that would setup each node class within a child class. This also would seem to work, however I still run into the problem of an easy method of testing leafs - calling a parent’s child’s child’s … leaf.
Ie. var node:Node = new Node(setPoint(…)); //sets 4 points, nw, ne, sw, se, and wd/ht
test = Node.getChild1(); // returns Node class
test = test.getChild1(); // returns Node class
…
array = test.getPoint(); // returns coordinations array, use for testing
Success? // Talk about recursive…
I have only tried my first thought - I kind’ve gave up after running in circles in my head and on paper. Ofcourse it always look good on paper, haha.
Thus, my question to my fellow users - anyone care to share their work on quadtrees? I don’t care what language, so long as it is fairly easy to grasp.
