Sign in to follow this  
Halsafar

Calculate Number of Nodes in a quad tree

Recommended Posts

Halsafar    205
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
ToohrVyk    1596
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
Halsafar    205
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