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 and a minimum halfsize. The most important options are:

• minvalues: minimum number of points required for a box before it is subdivided.
• maxprotrusion: maximum allowed protrusion of an element outside its box, normalized by 2*halfsize.
• computeprotrusion: functor used to compute protrusion.

For example, maxprotrusion=0.5 means no element may protrude by more than halfsize.

By default, computeprotrusion=ComputeProtrusionFunctor(), which treats elements as points and therefore gives zero protrusion. For more complex elements, provide a custom protrusion functor.

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

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1; minvalues=60, maxprotrusion=0.5)

TwoNTree{3, BoxData{3, Float64}, Float64}
 level: 1 with 1 node(s) with on average 1610.0 points and 8.0 children and halfsize: 1.6
- level: 2 with 8 node(s) with on average 201.25 points and 4.0 children and halfsize: 0.8
-- level: 3 with 32 node(s) with on average 50.31 points and 1.03 children and halfsize: 0.4
--- level: 4 with 33 node(s) with on average 19.06 points and 0.0 children and halfsize: 0.2

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

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.0; minvalues=60)

TwoNTree{3, BoxData{3, Float64}, Float64}
 level: 1 with 1 node(s) with on average 1610.0 points and 8.0 children and halfsize: 1.0
- level: 2 with 8 node(s) with on average 201.25 points and 7.12 children and halfsize: 0.5
-- level: 3 with 57 node(s) with on average 28.25 points and 0.0 children and halfsize: 0.25

In the Petrov-Galerkin case, the tree can be constructed by providing two sets of points

using CompScienceMeshes
using H2Trees

mx = meshsphere(1.0, 0.1)
my = meshsphere(2.0, 0.1)

tree = TwoNTree(vertices(mx), vertices(my), 0.1)

BlockTree{TwoNTree{3, BoxData{3, Float64}, Float64}}(TwoNTree{3, BoxData{3, Float64}, Float64}
 level: 2 with 1 node(s) with on average 1610.0 points and 8.0 children and halfsize: 1.6
- level: 3 with 8 node(s) with on average 201.25 points and 4.0 children and halfsize: 0.8
-- level: 4 with 32 node(s) with on average 50.31 points and 3.41 children and halfsize: 0.4
--- level: 5 with 109 node(s) with on average 14.77 points and 3.3 children and halfsize: 0.2
---- level: 6 with 360 node(s) with on average 4.47 points and 0.0 children and halfsize: 0.1
, TwoNTree{3, BoxData{3, Float64}, Float64}
 level: 1 with 1 node(s) with on average 6293.0 points and 8.0 children and halfsize: 3.2
- level: 2 with 8 node(s) with on average 786.62 points and 4.0 children and halfsize: 1.6
-- level: 3 with 32 node(s) with on average 196.66 points and 3.75 children and halfsize: 0.8
--- level: 4 with 120 node(s) with on average 52.44 points and 3.34 children and halfsize: 0.4
---- level: 5 with 401 node(s) with on average 15.69 points and 3.82 children and halfsize: 0.2
----- level: 6 with 1532 node(s) with on average 4.11 points and 0.0 children and halfsize: 0.1
)

This creates a BlockTree with two TwoNTrees.