Menu
I'm trying to implement a forward iterator for a quadtree. Unfortunately I don't seem to be able to find any resource about traversal in a quadtree.
Can anybody point me in the right direction?
315
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
The quadtree is an approach to image representation based on successive subdivision of the array into quadrants. In essence, the array is repeatedly subdivided into quadrants until blocks are obtained (possibly single pixels) which consist of entirely the same type of pixels.
Quadtrees are used in image compression, where each node contains the average colour of each of its children. The deeper you traverse in the tree, the more the detail of the image. Quadtrees are also used in searching for nodes in a two-dimensional area.
Quadtree is a way of partitioning space so that it's easy to traverse and search. A quadtree recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares. Each distinct data point exists in a unique leaf node; Coincident points are represented by a linked list.
An easy way is to linearize the tree. You'll have to do it recursively, of course, but you'll make an array of pointers to the nodes you want to visit and then create a forward iterator from that.
181
Take a gander at the following paper and see if it has what you need...
Simple and Efficient Traversal Methods for Quadtrees and Octrees
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
