Quadtree traversal

Question

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?

Specialize

Answer 1

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.

Foreword

So simple so good! How come I didn't think of doing this. Now btw, I'm facing problems with nodes with one of the index equal to its parent. Seems I have to change the insert rules or something. Any idea? – Specialize

Answer 2

Take a gander at the following paper and see if it has what you need...

Simple and Efficient Traversal Methods for Quadtrees and Octrees

Insertion

I gave this paper a quick try before asking. Maybe it was too quick. – Specialize

Answer 3

This is my implementation in javascript: https://github.com/alexroat/quadtree-traversal

There is a visual demo that shows the behaviour of the algorithm.

Brisance