TwoNTree

The TwoNTree is a $2^n$-tree for organizing points in $\mathbb{R}^n$. For 3D points, this is an octree.

You can build a TwoNTree from a set of points through the builder-based construction API. The most important TwoNTreeBuilder options are:

• minhalfsize: minimum half-size of a leaf box. The default 0 disables this stopping criterion.
• minvalues: minimum number of points required for a box before it is subdivided. The default is 70.
• protrusion: protrusion policy, see Protrusion Policy.

In the Galerkin case, the tree can be constructed as follows

m = meshsphere(1.0, 0.1)
tree = H2Trees.buildtree(
    vertices(m);
    builder=TwoNTreeBuilder(;
        minhalfsize=0.1,
        minvalues=60,
        protrusion=H2Trees.ProtrusionCheck(; max=0.5),
    ),
)

TwoNTree{3,Float64}
level   nodes         avg values    avg children  halfsize      
1       1             1610.0        8.0           1.6           
2       8             201.25        4.0           0.8           
3       32            50.31         1.03          0.4           
4       33            19.06         0.0           0.2           

Alternatively, the tree can be constructed with a minimum halfsize of 0:

m = meshsphere(1.0, 0.1)
tree = H2Trees.buildtree(vertices(m); builder=TwoNTreeBuilder(; minhalfsize=0.0, minvalues=60))

TwoNTree{3,Float64}
level   nodes         avg values    avg children  halfsize      
1       1             1610.0        8.0           1.0           
2       8             201.25        7.12          0.5           
3       57            28.25         0.0           0.25          

In the Petrov-Galerkin case, two sets of points build a BlockTree of two TwoNTrees instead — see BlockTree and Petrov Trees for construction and the level-scale invariant both sides must satisfy.

Internally, TwoNTree stores cached topology in a tree index; see Tree Access and Values for the accessor API.