Finding size of perfect quad tree
-
27-10-2019 - |
문제
I need to find the size of a perfect quad tree. This means I have 1 root node that splits into 4 nodes that splits into 4 nodes etc.
so a quad tree of height 1 would be size 1 height 2 = size 5 (1 + 4) height 3 = size 21 (1 + 4 + 16) height 4 = size 85 (1 + 4 + 16 + 64)
etc..
I know that the size of a perfect binary tree can be found with: size = 2^(height+1)-1 So I believe that a similar equation exists for quad tree.
So what is it?
해결책
This is a geometric series. So the relevant formula is:
S = a * (1 - r^n) / (1 - r)
where a
is the first value, r
is the common ratio, n
is the number of terms, and ^
denotes "to-the-power-of".
다른 팁
For a quad tree the algorithm is
((4^depth)-1)/3
For example with depth 3 you get
(64-1)/3 = 21
and if you count three layers you get
1 + 4 + 16 = 21
In my implementation I have even divided it into two arrays where the size for all nodes that arent leave nodes is
((4^(depth-1))-1)/3
and leave nodes is
4^(depth-1)
I do these calculations at compile time with meta programming for pow, and a template argument for the depth. So i just allocate my nodes in two arrays.
Just in case anyone will need a code sample (in swift3)
public func tileCount(forLevelRange levelRange: Range<UInt>) -> UInt64 {
var tileCount: UInt64 = 0
for level in levelRange.lowerBound ..< levelRange.upperBound {
tileCount += UInt64(pow(Double(1 << level), 2) )
}
return tileCount
}