Re: [Algorithms] Octree leaf neighbours

[Sam K. <sa...@ip...>]

Thatcher,

Ta for the reasurance, I'll give it a go and see what kind of speed I get.

The thing is, at the moment I'm not actually "storing the tree". I'm just
traversing it.  I need to share vertices between neighbouring leaves, and if
the only way to do this is by physically storing the tree and "jumping
around" to find the neighbour, so be it.

Thanks,

Sam.



>
>On Sat, 15 Jul 2000, Sam Kuhn wrote:
>
>> I'm creating an octree, and need to maintain pointers between
neighbouring
>> *leaves*, and do it quick. The only way I can think of is to skip back up
>> the tree and down the neighbouring branches to locate each of the 6
>> neighbours. This doesn't seem very fast.
>
>It's an O(1) operation on average according to something I read somewhere
>(I think Hanan Samet proved this in one of his books but I don't have a
>reference handy).  The outline of the proof would be something like: half
>of the time, the neighbor is a child of the immediate parent (i.e. one
>generation from a common ancestor); a quarter of the time the neighbor is
>two generations from a common ancestor; an eighth of the time it's three
>generations away, etc.  So over a large number of random queries (N), the
>cost is proportional to N * sum(i=1 --> N: 1/(2^i)).  Divide out the N to
>compute the average cost, and the sum approaches 1 as N approaches
>infinity.
>
>So while the traversal may *seem* slow when looking at the code, it
>probably isn't as slow as you think.
>
>--
>Thatcher Ulrich
>http://tulrich.com
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list