Sign in to follow this  
Halsafar

Calculate Number of Nodes in a quad tree

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this