Regular subpavings represent a special case of the general kd tree structure: a space partitioning data structure for organising points in k-dimensional space. We aim to combine interval analysis and inclusion functions with kd trees and manipulation of tree structures in order to use subpavings for statistical set processing.
We start with a re-implemention in C++ of a subpaving-as-a-binary-tree object based on [AIA2001]. Our new class is based on a class called SPnode, and a pointer to an SPnode is aliased as SubPaving. Again, we use C-XSC as the interval analysis library. This base class and functions are designed to also give us a basis for derived classes specifically designed for various forms of statistical set processing. Our new tree has links from child to parent as well as from parent to child (ie, each child knows who its parent is); this may be used in 'shrink' the tree, absorbing children back up into the parent.
Other new members of the SPnode class include nodeName. The nodeName is a used as a convenient way to assist human interpretation of a tree of nodes. A nodeName is based on the parent node's name suffixed with 'L' if the node is the left child of that parent and by 'R' if the node is the right child of that parent. A root node is usually named 'X'.
The SPnode class declarations and inline definitions are in the header file spnode.hpp. Other definitions are in the file spnode.cpp. Type definitions relevant to SPnodes are in the file sptypes.hpp. General tool functions useful for spnodes are in sptools.hpp and sptools.cpp. Algorithms used for set computation are declared in spalgorithms.hpp and defined in spalgorithms.hpp. Template functions requiring node concepts are in sptemplates.hpp.
A derived class based on the SPnode class can be used to reimplement the set computations described in AIA2001.
See:
We create new classes derived from the SPnode base class, each class a form of SPnode specialised for a particular kind of statistical set processing.
See: