\documentclass{article}
\usepackage[margin=1.0in]{geometry}
\usepackage{tikz}
\usetikzlibrary{fit}
\usetikzlibrary{positioning}
\usetikzlibrary{bending}
\usetikzlibrary {arrows.meta} 
\usetikzlibrary {shapes.symbols} 
\usetikzlibrary {shapes.geometric}
\usetikzlibrary {shapes.multipart} 
% \usetikzlibrary{external}
% \tikzexternalize % activate!

\tikzset{
  treenode/.style= {
    circle,
    color = black!30,
    draw,
    fill = yellow!30,
    line width = 1mm,
    inner xsep = 3mm,
    inner ysep = 3mm
  },
  pointcloud/.style= {
    cloud,
    cloud ignores aspect,
    cloud puffs=11,
    color = black!30,
    draw,
    fill = yellow!30,
    line width = 1mm,
    inner xsep = 3mm,
    inner ysep = 3mm
  },
  disjointdataset/.style= {
    rectangle split,
    rectangle split parts=#1,
    rectangle split horizontal,
    draw,
    anchor=center,
  },
  namedpcs/.pic = {
    \node[pointcloud] (-pc1) {``PC1''};
    \node[pointcloud,below=0.0mm of -pc1.mid] (-pc2) {``PC2''};
  }

}

\begin{document}

\section{Preliminaries}

A \textbf{point cloud} is of type \texttt{PointCloud::Dataset} which is effectively a \texttt{std::map<std::string, Array>}.  An \texttt{Array} is contiguous storage with a dynamic numerical type.


\begin{center}
\begin{tikzpicture}
  \node[pointcloud] {pointcloud};
\end{tikzpicture}
\end{center}

A may aggregate many point clouds into a \textbf{named point cloud set} is a \texttt{std::map<std::string,Dataset>}.

\begin{center}
\begin{tikzpicture}
  \pic (pcA)  {namedpcs};
\end{tikzpicture}
\end{center}

We may also \textbf{concatenate} point clouds \textbf{by reference} (light weight, no copy) into a \textbf{PointCloud::DisjointDataset}.

\begin{center}
\begin{tikzpicture}[disjointdataset/.style={
    rectangle split,
    rectangle split parts=#1,
    rectangle split horizontal,
    draw, anchor=center}]
  \node[disjointdataset=2] {ref(PC $1_a$)\nodepart{two}ref(PC $1_b$)};
\end{tikzpicture}
\end{center}

And we may combine the two aggregations \texttt{std::map<std::string, DisjointDataset}.  In the context of the a \textbf{point cloud tree} we will call these \textbf{scoped point clouds}.

\section{N-ary tree}

We now turn to generic \textit{n-ary} trees.  
A tree is composed of nodes.

\begin{center}
\begin{tikzpicture}
  \node[treenode] {node};
\end{tikzpicture}
\end{center}

And we will define a node to have \textbf{three parts}.  First, we allow a node to hold a \textbf{value} (aka ``payload'') object.  

\begin{center}
\begin{tikzpicture}
  \node[treenode] (node) {node};
  \node[right=of node,draw=black!30,line width=1mm,rounded corners] (value) {value};

  \draw[->] (node) edge (value);
\end{tikzpicture}
\end{center}

Ownership is indicated by the \textbf{solid arrow}.

Next, we say a node has \textbf{zero or one parent nodes} and a node has \textbf{zero or more children nodes}.
A tree that requires any node to have no more than two children nodes is a ``binary tree''.  A general or n-ary tree allows ``n'' children.

We cause a node to \textbf{own its children nodes} and a node will \textbf{reference its parent node}.  The children are organized into an ordered list so children nodes \textbf{reference their neighboring siblings}.
A tree with three nodes, one parent and two children are illustrated.  A reference is indicated with \textbf{dashed arrow}.
Again, while only two children are drawn, an n-ary tree node may have zero or more.

\begin{center}
\begin{tikzpicture}[level/.style={sibling distance=40mm/#1}]
  \node[treenode] (r) {root}
  [level distance=30mm]
  child {
    node[treenode] (a) {A}
    edge from parent [<-,dashed]
    node[above,draw=none,sloped] {parent}
  }
  child {
    node[treenode] (b) {B}
    edge from parent [<-,dashed]
    node[above,draw=none,sloped] {parent}
  };
  \draw[dashed,<->] (a) -- node[below]{siblings} (b) ;

  \node[draw=black!30,line width=1mm,rounded corners,fit=(a) (b)] (children) {};
  \draw[->] (r) -- node[above,sloped]{children} (children);

  \node[below=10mm of a] (pcA) {A's value};
  \node[draw=black!30,line width=1mm,rounded corners,fit=(pcA)] (aval) {};
  \draw[->] (a) -- (aval) ;

  \node[below=10mm of b] (pcB) {B's value};
  \node[draw=black!30,line width=1mm,rounded corners,fit=(pcB)] (bval) {};
  \draw[->] (b) -- (bval) ;

  \node[right=10mm of r] (pcR) {root's value};
  \node[draw=black!30,line width=1mm,rounded corners,fit=(pcR)] (rval) {};
  \draw[->] (r) -- (rval) ;

\end{tikzpicture}
\end{center}

As implemented here, \textbf{a tree is just its nodes}.  There is no ``tree object'' per se.   Rather, if code holds a ``root'' node then that code may access all nodes in the tree.  This may involve a manual navigation of the child/parent/sibling edges.  But, most conveniently this is done with a \textbf{tree descent iteration}.  

A \textbf{depth-first descent} iteration is implemented.  A descent may visit a node and all its descendants.  A descent may also be limited to a maximum depth.  For example a descent on a root note with a depth of unity (1) will visit only that root node.  A descent with a depth of two will visit the root and its direct children.  A depth of three will also include grandchildren, etc.  The special depth of zero marks unlimited descent.

A node with parent may be removed from the tree.  The removed node will be removed from its parent's collection of children, its neighbor siblings will themselves become neighbors and the removed node will no longer have a parent.  This removed node then becomes a root node of a tree holding its descendants (if any).
Conversely, a new node may be added as a child to any node.  

\section{Point cloud tree}

A \textbf{point cloud tree} or \textbf{point tree} is an n-ary tree with a \textbf{node value} type that provides storage and management of \textbf{point clouds} and \textbf{k-d trees} formed on them. 
This layer of functionality is provided by a \textbf{node value} of type \texttt{PointCloud::Tree::Points}.  It primarily consists of three parts:

\begin{enumerate}
  \item a set of ``local'' named point clouds
  \item a set of ``scoped'' point clouds
  \item a set of ``scoped'' k-d trees built on the scoped PCs
\end{enumerate}

We will described ``scoped'' below.  First, these three parts of the point cloud tree node value are illustrated.

\begin{center}
\begin{tikzpicture}[level/.style={sibling distance=40mm/#1}]

  % local PCs
  \pic (pcA) {namedpcs};
  \node[draw=black!30,line width=1mm,rounded corners,fit=(pcA-pc1) (pcA-pc2)] (pcval) {};
  \node[above=1mm of pcval,text width=3cm] (pclab) {local named PCs \texttt{string}$\to$\texttt{Dataset}};
  
  % scoped PCs
  \node[disjointdataset=3,below=20mm of pcval] (djds1) {
    ref(PC ABC$_a$)\nodepart{two}ref(PC ABC$_b$)\nodepart{three}...};
  \node[left=1mm of djds1] (djds1n) {PC ABC:};
  \node[disjointdataset=3,below=5mm of djds1] (djds2) {
    ref(PC XYZ$_a$)\nodepart{two}ref(PC XYZ$_b$)\nodepart{three}...};
  \node[left=1mm of djds2] (djds2n) {PC XYZ:};
  \node[draw=black!30,line width=1mm,rounded corners,fit=(djds1) (djds2) (djds1n) (djds2n)] (djdsval) {};
  \node[above=1mm of djdsval,align=center,text width=4cm] (djds) {scoped PCs \texttt{string}$\to$\texttt{DisjointDataset}};

  % scoped k-d trees
  \node[starburst, draw, below=20mm of djdsval,align=center,text width=3.5cm] (kd) {
    scoped k-d tree on PC1 disjoint dataset};

  \node[draw=black!30,line width=1mm,rounded corners,fit=(kd)] (kdval) {};
  \node[above=1mm of kd, text width=4.5cm,align=center] (kdlab) {k-d trees on scoped PCs \texttt{string}$\to$\texttt{NFKD} (nanoflann)};

  % \draw[dashed,out=45,in=-90,looseness=1,<-] (pcA-pc2) edge (djds.one south);
  % \draw[dashed,out=45,in=-90,looseness=1,<-] (pcB-pc2) edge (djds.two south);
  % \draw[dashed,out=0,in=0,looseness=2,->] (kd) edge (djds.two east);

  \node[draw=black!30,line width=1mm,rounded corners,fit=(kdlab) (kdval) (djdsval) (pcval) (pclab)] (allval) {};
  \node[align=center,above=1mm of allval,text width=4cm] {PC tree node value type \texttt{PointCloud::Tree::Points}};

  \node[treenode,left=of allval] (node) {node};
  \draw[->] (node) edge (allval);

\end{tikzpicture}
\end{center}

\section{Point cloud tree scope}

A \textbf{scope} is the information that describes a selection of a subset of the data in a point cloud tree.  Selected data is said to be ``in scope''.  A scope is defined independently of any tree node but is interpreted respect to a given tree node.  This node is considered the ``root'' of the scope.  A scope is defined by three items:

\begin{enumerate}
\item A depth-first descent iteration depth as described above.
\item A name of a node-local point cloud.
\item A list of names of point cloud arrays to use as k-d tree coordinates.
\end{enumerate}

A scope may be applied to a point cloud tree to produce a representation of a point cloud called a 
\textbf{scoped point cloud}.  A scoped point cloud is represented by a \texttt{DisjointDataset} which is a light-weight collection of references to individual point clouds each represented by \texttt{Dataset}.
The construction of the scoped point cloud follows these rules:

\begin{enumerate}
\item A node is provided as the root of the scope.
\item A depth-first descent iteration begins at the root node.
\item The depth of the descent is limited by the scope's \texttt{.depth} value.
\item If a visited node lacks a local point cloud with the name given by the scope it is ignored and the iteration continues.
\item If a visited node lacks an array for each coordinate name given in the scope an exception is raised.
\item The node is considered ``in scope'' and its named local point cloud is appended to the scoped point cloud.
\end{enumerate}

A \textbf{scoped k-d tree} is built upon a \textbf{scoped point cloud} of the same scope and using the named scope arrays as coordinates.  A scoped point cloud may be created without an accompanying scoped k-d tree.  Conversely, creating a scoped k-d tree will use an existing or automatically create the corresponding scoped point cloud.

\section{Example}

A small point cloud tree is illustrated.  The ``root'' node has two children labeled ``A'' and ``B'' in the diagram.  Each child has a set of point clouds with the names ``PC1'' and ``PC2''.  The user requests, via the value of the ``root'' node, a scoped point cloud with a scope name of ``PC2'',  depth not equal to one and a list of point cloud array names (not illustrated).  The value of the ``root'' node performs a depth-first descent iteration collecting ``PC2'' from children ``A'' and ``B'' as they are in scope, construct, stores and returns the lightweight disjoint dataset as the scoped point cloud.  The user may later request a k-d tree in the same scope.  This will use the previously created scoped point cloud.  Had it not been previously constructed it would be made as a side-effect to constructing the scoped k-d tree.


\begin{center}
\begin{tikzpicture}[level/.style={sibling distance=40mm/#1}]
  \node[treenode] (r) {root}
  [level distance=30mm]
  child {
    node[treenode] (a) {A}
    edge from parent [<-,dashed]
    node[above,draw=none,sloped] {parent}
  }
  child {
    node[treenode] (b) {B}
    edge from parent [<-,dashed]
    node[above,draw=none,sloped] {parent}
  };
  \draw[dashed,<->] (a) -- node[below]{siblings} (b) ;

  \node[draw=black!30,line width=1mm,rounded corners,fit=(a) (b)] (children) {};
  \draw[->] (r) -- node[above,sloped]{children} (children);

  \pic (pcA) [below right=20mm of a] {namedpcs};
  \node[draw=black!30,line width=1mm,rounded corners,fit=(pcA-pc1) (pcA-pc2)] (aval) {};
  \draw[->] (a) -- (aval) ;
  \node[below=0.1mm of aval] {A's value};

  \pic (pcB) [below right=20mm of b] {namedpcs};
  \node[draw=black!30,line width=1mm,rounded corners,fit=(pcB-pc1) (pcB-pc2)] (bval) {};
  \draw[->] (b) -- (bval) ;
  \node[below=0.1mm of bval] {B's value};

  \node[disjointdataset=2,right=20mm of r] (djds) {
    ref(A:PC2)\nodepart{two}ref(B:PC2)};
  \draw[->] (r) -- (djds) ;
  \node[above=0.1mm of djds]{PC2 disjoint dataset};

  \node[starburst, draw, above=10mm of djds,align=center,text width=3.5cm] (kd) {
    scoped k-d tree on PC2 disjoint dataset};
  \draw[->] (r) -- (kd) ;

  \draw[dashed,out=45,in=-90,looseness=1,<-] (pcA-pc2) edge (djds.one south);
  \draw[dashed,out=45,in=-90,looseness=1,<-] (pcB-pc2) edge (djds.two south);
  \draw[dashed,out=0,in=0,looseness=2,->] (kd) edge (djds.two east);

  \node[draw=black!30,line width=1mm,rounded corners,fit=(djds) (kd)] (rval) {};
  \node[above=1mm of rval] {root's value};
\end{tikzpicture}
\end{center}

\section{Dynamic actions}

A point cloud tree supports node insertion and removal with some caveats. 
For lowest developer cognitive burden, do not modify the tree after requesting any scoped objects. 
Insertion and removal of nodes may update existing scoped objects to which the caller may hold reference.  The caveats are now described.

Insertion is performed such that if the node is in scope for any existing scoped point clouds or scoped k-d trees these objects will be updated.  While the initial construction of a scoped point cloud reflects the order of the depth-first descent iteration a later update will effectively append  the new local point cloud of the inserted node to the existing scoped point cloud and/or scoped k-d tree.  

Removal is less sophisticated and stable.  Removing a node that is in scope for existing scoped point clouds or scoped k-d trees will invalidate these objects.  The invalidation is lazy.  That is, any existing handles on these objects will not reflect the removal.  If the scoped object is retrieved again from the node or if an in-scope descendant node is added the scoped object is rebuilt.  The order of points in the scoped object will reflect a fresh depth-first descent.  Any references to any point ordering held by the caller must be considered invalid.


\end{document}
