• Advertisement
Sign in to follow this  

Calculate Number of Nodes in a quad tree

This topic is 4643 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Okay I can figure out the number of leaves, for a 257x257 heightmap. (256 / iLeafWidth) * (256 / iLeafWidth) Now I have a way of calculating the number of nodes which I believe is flawed, it only produces the right number when iLeafWidth is 4. Then again I cannot proove this, since I do not know how to sit down on paper and find out exactly how many nodes I will have total...

Share this post


Link to post
Share on other sites
Advertisement
Consider that the depth of your root is 0, and there is only one root so x0 = 1.

If you have xn nodes at depth n, then you will have xn+1 = 4 xn nodes at depth n+1.

This ends up being: xn = 4n for any n.

That is, unless the nodes at depth n are leaves, at which point they have no children. Let L be the depth of leaves. Then the number of nodes you have is:

X = Σ0..L 4n = (4L+1 - 1) / 3

In any case, L = log4 leafCount, so:

X = (4 * leafCount - 1) / 3

Share this post


Link to post
Share on other sites
Genious explanation!
After I posted this I did solve the problem in my function but it still has inaccurate moments due to the some dividing which takes place.

I em going to impliment what you have posted.

Thanks.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement