by Hi
I just wanted to let know the people using a quadtree datastructure that
I
set up a web site containing C++ source code, man pages and
documentation
for a linear quadtree. The nice thing about this quadtree is that the
nodes can
be browsed in constant time, namely, each move in the quadtree has the
exact
computational cost of ONE addition. Any traversal of the nodes can be
implemented, for ex. I solved the coplanarity problem of hierarchical
triangulation
in optimal computational time in
http://lcavwww.epfl.ch/~balmelli/downloads/vmv99.ps.gz
The code is very simple to use, the nodes are traversed with simple
function
like "goNorth", "goSouth"... any browsing can be implemented. The method
to
obtain the constant time property is described in
http://lcavwww.epfl.ch/~balmelli/downloads/quadtree.ps.gz
I use the quadtree in computer graphics to store hierarchical meshes
built on terrain
data. The quadtree is also very useful in image processing, compression,
digital signal processing.
The quadtree is organized as A SPATIAL DATASTRUCTURE, which makes it
very
useful to store such kind of spatially organized data.
Download the code on the website and register! I am not representing a
company, i'm
only a phd student, so your email will not be used for any commercial
purpose. :)))
Registered people will receive update of code, and a soon-to-come Java
applet
demonstrating the quadtree usage. The website is at
http://lcavwww.epfl.ch/~balmelli/software/quadtree/index.html
enjoy, any comments are welcome!
all the best,
Laurent Balmelli
Ecole Polytechnique Federal de Lausanne