RE: [Algorithms] Quadtree / Octtree neighbors

[Kelvin M. <ke...@re...>]

Thanks, i'd forgotten about that thread even though I'd read it.

I was thinking of implementing a method where you figured out the tree
transversal of of your six neighbors *as if* your octree was subdivided
equally.  Then transversing down the actual tree for each 'potential'
neighbor.  If you can't reach it then you've found a neighbor and add it to
your neighbor list.  If you reach it but it's not a leaf node then countinue
transvering down the relavanet directions only (ie: if you're searching for
the north bordering node then transverse down all the south (southeast,
southwest, etc.) nodes until you reach leave nodes.  Add the leaves.

The method you describe below seems to be simular except I start transversal
at the root and go down where as you go up and then down.

I noticed in the 'octree leaf neighbors' thread is was mentioned that you
have 6 neighbors.   Isn't this number is variable?


-----Original Message-----
From: Sam Kuhn [mailto:sa...@ip...]
Sent: Friday, August 04, 2000 5:40 AM
To: gda...@li...
Subject: Re: [Algorithms] Quadtree / Octtree neighbors


Kelvin,

We had a bit of a discussion on exactly this a couple of weeks ago, check
the archive and see if you can find anything of use.

I *think* we established that other than using a cubic hash table (for the
octree case) indexed by position of a node in 3d, and using up tons of
memory, that the only way to achieve this is to jump back up the tree and
down neighbouring branches to find connectivity. But as Thatcher mentions,
this probably isn't as bad as it would seem, like half the time you are
jumping up one level, a quater of the time 2 levels, a 8th of the time 3
etc.. Check his post for more on this.

If you find anything else, I'd be interested in hearing it.

Regards,

Sam Kuhn
I!Play Ltd.
sa...@ip...



-----Original Message-----
From: Kelvin McDowell <ke...@re...>
To: 'gda...@li...'
<gda...@li...>
Date: 03 August 2000 8:52 PM
Subject: [Algorithms] Quadtree / Octtree neighbors


>I need to construct a graph which connects all the neighboring nodes of a
>quadtree and octree.  For each leaf node I need to determine all the other
>leaves that border on it.  Does anyone know of an elegant way of doing
this?
>
>Kelvin McDowell
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list