SPMinimalnodes are nodes in the representation of a subpaving as a minimal binary tree. More...

Inheritance diagram for subpavings::SPMinimalnode:

Collaboration diagram for subpavings::SPMinimalnode:

Public Member Functions
	SPMinimalnode ()
	Default constructor.
	SPMinimalnode (ivector &v)
	Initialised constructor with box.
	SPMinimalnode (LabBox &lb)
	Initialised constructor. Initialised with a LabBox (labeled box).
	SPMinimalnode (const SPMinimalnode &other)
	Copy constructor.
virtual	~SPMinimalnode ()
	Destructor. Declare as virtual because we may use SPMinimalnode as a base class.
SPMinimalnode &	operator= (SPMinimalnode rhs)
	Copy assignment operator.
void	nodeReunite (SPMinimalnode lChild, SPMinimalnode rChild)
	Tries to reunite nodes to form a minimal subpaving.
void	nodeAdoptLeft (SPMinimalnode *lChild)
	Builds a higher level of a tree from existing nodes.
void	nodeAdoptRight (SPMinimalnode *rChild)
	Builds a higher level of a tree from existing nodes.
virtual BOOL_INTERVAL	spContains (const ivector &z) const
	Check if ivector z is contained in this or children.
virtual BOOL_INTERVAL	spContains (const rvector &p) const
	Check if rvector p is contained in this node or any of its children.
void	swapMin (SPMinimalnode &spn)
Accessors for links between the nodes.
These accessor methods shadow equivalent methods in the base class. Thus the method used is determined at compile time, not run time as would be the case if virtual methods were used. Because the pointers to parents and children are part of the base class definition, the methods have to cast the base class form to the derived class form in order for the pointer returned to be able to be used with derived class members. Note that pointers for parent, leftChild, and rightChild are not reference counted so there could potentially be problems with the use of returned pointers (for instance, being used to delete nodes). These pointers might be better implemented with boost::shared_ptr .
SPMinimalnode *	getParent () const
	Accessor for the parent of a node.
SPMinimalnode *	getLeftChild () const
	Accessor for the left child of a node.
SPMinimalnode *	getRightChild () const
	Accessor for the right child of a node.
Static Public Member Functions
static BoxVec &	vecLeafBoxOuterJacket (BoxVec &boxes, const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static SPMinimalnode *	spLeafBoxOuterJacket (const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static double	volOuterJacket (const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static BoxVec &	vecLeafBoxIntersection (BoxVec &boxes, const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static SPMinimalnode *	spLeafBoxIntersection (const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static double	volIntersection (const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static BoxVec &	vecLeafBoxDifference (BoxVec &boxes, const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static BoxVec &	vecBoxNodeDifference (BoxVec &boxes, ivector box1, const SPMinimalnode *const spn2)
static SPMinimalnode *	spLeafBoxDifference (const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static double	volDifference (const SPMinimalnode const spn1, const SPMinimalnode const spn2)
static SPMinimalnode *	makeTreeFromLeaves (ivector &root, ImageList &leafList)
	Forms a minimal SPMinimalnode subpaving from leaf boxes.
static SPMinimalnode *	makeTreeFromVoxels (ivector &root, ImageList &leafList, double spacing, size_t dim)
	Forms a minimal SPMinimalnode subpaving from voxel boxes.
static SPMinimalnode *	vtkPaving (const std::string filename)
	Make a subpaving from vtk file data.
Related Functions
(Note that these are not member functions.)
SPMinimalnode *	Sivia (PIBT BoolTest, const SPMinimalnode const toInvert, SPMinimalnode const search, const double eps)
	Set Inversion Via Interval Analysis.
SPMinimalnode *	ImageSp (PIVF f, SPMinimalnode *spn, double eps)
	Creation of image subpaving with Interval Analysis.

Detailed Description

SPMinimalnodes are nodes in the representation of a subpaving as a minimal binary tree.

A minimal tree means that a node will have at most one leaf child (ie, no node has two leaf or terminal children).

A node represents a box (interval vector). SPMinimalnodes are linked together to form the tree. The initial box of the subpaving is the box represented by the root node of the tree. A box which has been split will be represented as node with one or two children.

A subpaving of [x] (union of non-overlapping subboxes of [x]) is represented by the leaves (degenerate/ child-less) nodes in the tree.

SPMinimalnodes are an adaptation of the AIASPnode class [from Jaulin, Kieffer, Didrit and Walter, Applied Interval Analysis, Springer, 2001, p. 336-348] including changes in coding, class members, and class structure. SPMinimalnodes are implemented under C-XSC.

This class replicates the set computation functionality of the subpaving nodes developed by [Jaulin, Kieffer, Didrit and Walter, Applied Interval Analysis, Springer, 2001] but also provides some additional functionality.

Constructor & Destructor Documentation

SPMinimalnode::SPMinimalnode ( ivector & v ) [explicit]

Initialised constructor with box.

Initialised with one interval vector for the box.

                                       : SPnode(v)
{ }

Member Function Documentation

SPMinimalnode * SPMinimalnode::getLeftChild ( ) const

Accessor for the left child of a node.

Hides the base class version of this method.

Returns a copy of the pointer to leftChild node.

Reimplemented from subpavings::SPnode.

{ return (SPMinimalnode*) leftChild; }

SPMinimalnode * SPMinimalnode::getParent ( ) const

Accessor for the parent of a node.

Hides the base class version of this method.

Returns a copy of the pointer to parent node.

Reimplemented from subpavings::SPnode.

{ return (SPMinimalnode*) parent; }

SPMinimalnode * SPMinimalnode::getRightChild ( ) const

Accessor for the right child of a node.

Hides the base class version of this method.

Returns a copy of the pointer to rightChild node.

Reimplemented from subpavings::SPnode.

{ return (SPMinimalnode*) rightChild; }

SPMinimalnode * SPMinimalnode::makeTreeFromLeaves	(	ivector &	root,
		ImageList &	leafList
	)		`[static]`

Forms a minimal SPMinimalnode subpaving from leaf boxes.

Make a minimal subpaving tree from a list of interval vectors which are represented by leaves of the tree. The root of the subpaving tree will have Box = root, and the leaves in the list will be formable by a series of bisections of the given root.

MakeTreeFromLeaves is applied recursively on bisected halves of root and new lists there are no boxes in the list.

Uses Reunite() and recursive calls to MakeTreeFromLeaves() to work upwards to form a minimal subpaving tree.

Parameters:

root	the root of the tree.
leafList	a collection of non-overlapping interval vector leaves each of which can be formed by series of bisections of the given root.

Returns:: a regular minimal subpaving with rootbox root.

{
  SPMinimalnode* newNode = NULL;  // for return value
  
  try {

    if (!leafList.empty())
    {
      //sort using the volCompare function
      leafList.sort(volCompare);   // sorts smallest to largest

      // test if root is equal to the largest image element, ie the last
      bool isRootEqual = (root == *leafList.rbegin());

      double smallestVol = Volume(*leafList.begin());

      //is root smaller than twice the size of the smallest box in it
      bool isRootSmall = (Volume(root) < 2*smallestVol);

      // if the list has some images in it
      // and if the root is equal to the largest box in the list
      // or the root is close enough
      // return a new node based on root
      if (isRootEqual || isRootSmall) {

        newNode = new SPMinimalnode(root);
        
      }
      // if the list has some images in it
      // and the root is not equal to the largest box in the list
      // and the root is not small
      // bisect the root, divide up the list, and recurse

      if (!isRootEqual && !isRootSmall) {

        int maxdiamcomp = 0;
        double rootDiam = MaxDiam(root, maxdiamcomp);
        // new ivectors from splitting root along its biggest dimension
        ivector leftbox = Lower(root, maxdiamcomp);
        ivector rightbox = Upper(root, maxdiamcomp);

        // create two empty lists for the left and right side
        ImageList leftlist, rightlist;

        ImageListItr it; // iterator to for the list

        // iterate through the current list, put the intersection of any
        // element with the leftbox into new left list, & intersection
        // of any element with the new right box into new right list
        // but only put in whole leaves, ie with vol >= smallest vol
        for (it=leafList.begin(); it!=leafList.end(); it++) {
          ivector interLeft;  // intersection with left hull
          ivector interRight;  // intersection with right hull

          if (Intersection(interLeft, *it, leftbox)) {
            if (Volume(interLeft) > 0.5*smallestVol)
              leftlist.push_back(interLeft);
          }

          if (Intersection(interRight, *it, rightbox)) {
            if (Volume(interRight) > 0.5*smallestVol)
              rightlist.push_back(interRight);
          }

        } // end of iteration through list elements

        // recursively call makeTreeFromLeaves with leftbox, leftlist
        // and rightbox, rightlist
        // reunite the results using root as the box for parent node
        // makeTreeFromLeavess creates a minimal subpaving
        // (no sibling child nodes) on the root

        newNode = Reunite<SPMinimalnode>(makeTreeFromLeaves(leftbox,leftlist),
                  makeTreeFromLeaves(rightbox, rightlist),
                                root);

      } // end of is list has elements and first box not root
    }

    // if there is nothing in the list we return the default
      // initialisation value of NULL

    return newNode;
  }
  catch(std::exception const& e) {
    delete newNode;
    newNode = NULL;
    throw;
  }

}

SPMinimalnode * SPMinimalnode::makeTreeFromVoxels	(	ivector &	root,
		ImageList &	leafList,
		double	spacing,
		size_t	dim
	)		`[static]`

Forms a minimal SPMinimalnode subpaving from voxel boxes.

Make a minimal subpaving tree from a list of interval vectors which approximate the leaves of the tree. The root of the subpaving tree will have Box = root, and the leaves in the list will have the same width in each dimension and be formable by a series of bisections of the given root. i.e. each leaf will be the same size as each other leaf and will be a equal-sided hypercube.

MakeTreeFromVoxels is applied recursively on bisected halves of root and new lists until either there are no boxes in the list or the largest diameter of the root the smallest we would expect given spacing or the root is equal to the largest box in the list.

Uses Reunite() and recursive calls to MakeTreeFromVoxels() to work upwards to form a minimal subpaving tree

Parameters:

root	the root of the tree.
leafList	a collection of non-overlapping interval vector leaves each of which is approximately the same as the boxes formed by series of bisections of the given root.
spacing	is the spacing from the voxel data, ie the number of voxels in any dimension (assumed to be the same for all dimensions).
dim	is the number of dimensions we are using.

Returns:: a regular minimal subpaving with rootbox root.

{
  SPMinimalnode* newNode = NULL;  // for return value
  
  try {

    if (!leafList.empty()) {
      //sort using the volCompare function
      leafList.sort(volCompare);   // sorts smallest to largest

       // test if root is equal to the largest image element, ie the last
      bool isRootEqual = (root == *leafList.rbegin());

      // with given spacing, max width in any should be 1/spacing
      // so as soon as max root dimension is below 2/spacing, it should
      // be in the subpaving if it has any image data in it
      // so be conservative and take 1.5/spacing (between 1/ and 2/)
      double eps = 1.5/spacing;
      int maxdiamcomp = 0;  // to take value calculated from MaxDiam
      // find the maximum diameter, put the max dimension into maxdiamcomp
      double maxDiamRoot = MaxDiam(root, maxdiamcomp);

      // test if maximum root width is smaller than eps
      bool isRootSmall = (maxDiamRoot < eps);

      // if the list has some images in it
      // and either if the root is equal to the largest box in the list
      // or if the root max diameter is < eps
      // return a new node based on root
      if (isRootEqual || isRootSmall) {

         newNode = new SPMinimalnode(root);
         
      }
      // if the list has some images in it
      // and the root is not equal to the largest box in the list
      // and the root is not small
      // bisect the root, divide up the list, and recurse
      else {

        // new ivectors from splitting root along its biggest dimension
        ivector leftbox = Lower(root, maxdiamcomp);
        ivector rightbox = Upper(root, maxdiamcomp);

        // create two empty lists for the left and right side
        ImageList leftlist, rightlist;

        ImageListItr it; // iterator to for the list

        // find a conservative minimum expected volume for a leaf as
        // half of the product of 1/spacing over all dimensions
        // we expect leaves to be the result of successive bisections so
        // if the volume of the intersection is not what we expect
        // then the intersection will be just the boundary
        real minVol = 0.5;
        for (size_t i = 0; i < dim; i++) minVol /= spacing;

        // iterate through the current list, put the intersection of any
        // element with the leftbox into new left list, & intersection
        // of any element with the new right box into new right list
        for (it=leafList.begin(); it!=leafList.end(); it++) {
          ivector interLeft;  // intersection with left hull
          ivector interRight;  // intersection with right hull

          if (Intersection(interLeft, *it, leftbox)) {
            if (Volume(interLeft) > minVol)
              leftlist.push_back(interLeft);
          }

          if (Intersection(interRight, *it, rightbox)) {
            if (Volume(interRight) > minVol)
              rightlist.push_back(interRight);
          }

        } // end of iteration through list elements

        // recursively call makeTreeFromVoxels with leftbox, leftlist
        // and rightbox, rightlist
        // reunite the results using root as the box for parent node
        // makeTreeFromVoxels creates a minimal subpaving
        // (no sibling child nodes) on the root

        newNode = Reunite<SPMinimalnode>(makeTreeFromVoxels(leftbox,
                        leftlist, spacing, dim),
                  makeTreeFromVoxels(rightbox,
                        rightlist, spacing, dim), root);

      } // end of is list has elements and first box does not contain root
    }

    // if there is nothing in the list we return the default
      // initialisation value of NULL

    return newNode;
  }
  catch(std::exception const& e) {
    delete newNode;
    newNode = NULL;
    throw;
  }
  

}

void SPMinimalnode::nodeAdoptLeft ( SPMinimalnode * lChild )

Builds a higher level of a tree from existing nodes.

This adopts a left child rather than attempting. to reunite two children into this.

{
  // *this is the node which will become the parent

  // point parent and child pointers in the right directions
  // nodeAddLeft() checks labels, hull size, present children
  nodeAddLeft(lChild);
}

void SPMinimalnode::nodeAdoptRight ( SPMinimalnode * rChild )

Builds a higher level of a tree from existing nodes.

This adopts a right child rather than attempting. to reunite two children into this.

{
  // *this is the node which will become the parent

  // point parent and child pointers in the right directions
  // nodeAddRight() checks labels, hull size, present children
  nodeAddRight(rChild);
}

void SPMinimalnode::nodeReunite	(	SPMinimalnode *	lChild,
		SPMinimalnode *	rChild
	)

Tries to reunite nodes to form a minimal subpaving.

Note that the nodes provided, lChild and rChild, are not the actual children of this, they are potential children which we are trying to either totally bring into this (if there are two of them) or to graft onto this if there is only one of them or if they are not both leaves, ie creating a minimal subpaving.

This is typically a new, part-formed node whose formation can be completed by reuniting already two already-formed nodes into it or by adding on one child if only one is available. nodeReunite is used in building a tree upwards (rather than in pruning leaves of formed tree from the bottom up).

If two potential children are provided and they are both leaves, it combines the two leaf siblings into this. If the potential children are not leaves or if only one potential child is provided, it grafts the potential child/children onto this as its child/children.

{
  // *this is the node which will become the parent

  // if both subpavings are leaves and hull of boxes is x,
  // discard them: *this is a leaf
  if (lChild->isLeaf() && rChild->isLeaf()) {
    if (*theBox !=
      (*(lChild->theBox) | *(rChild->theBox))) {
      throw subpavings::IncompatibleDimensions_Error(
            "nodeReunite(SPMinimalnode*, SPMinimalnode*)");
    }

    //discard the two subpavings given
    delete lChild;
    lChild = NULL;
    delete rChild;
    rChild = NULL;
  }

  else {  // at least one of the children is not a leaf
    // this has to adopt them rather than reuniting them
    nodeAdoptLeft(lChild);
    nodeAdoptRight(rChild);
    recursiveRename(); // recursively rename child branches
  }
}

BOOL_INTERVAL SPMinimalnode::spContains ( const ivector & z ) const [virtual]

Check if ivector z is contained in this or children.

Note that this checks not only the box represented by this node but the children as well. Returns a BOOL_INTERVAL type, ie can be true, false, or indeterminate (indeterminate if the ivector covers the border of the subpaving).

{
  // z is assumed not to be empty
  // nb Intersection() gives error if unequal index sets passed

  BOOL_INTERVAL retValue = BI_FALSE; // for the return value

  // case of a non-empty leaf
  if (!isEmpty() && isLeaf()) {

    ivector r; // temporary,to be passed to Intersection

    if (z<=getBox()) {
      retValue = BI_TRUE;
    }

    // result is indeterminate if there is an
    // intersection but z is not wholly in theBox
    else if (Intersection(r, z, getBox())) {
      retValue = BI_INDET;
    }

    // Case that there is no intersection
    else retValue = BI_FALSE;

  } // end (!isEmpty() && isLeaf())

  //case of an non-empty non-leaf
  if (!isEmpty() && !isLeaf()) {
  //

    ivector Lz, Rz; // ivectors passed to Intersection()
    // will contain intersection after Intersection() call

    // to hold results of tests on left and right children
    BOOL_INTERVAL Ltest = BI_FALSE;
    BOOL_INTERVAL Rtest = BI_FALSE;

    // indicators for tested left and right sides
    bool LtestSuccess = false;
    bool RtestSuccess = false;

    // Find if there is a leftChild with a box
    if (hasLCwithBox() &&
      Intersection(Lz, z, leftChild->getBox())) {
      // Lz contains intersctn of z & leftChild box

      // test Lz and left child node
      Ltest = (getLeftChild()->spContains(Lz));
      LtestSuccess = true;
    }


    // Find if there is a rightChild with a box
    if (hasRCwithBox() &&
      Intersection(Rz, z, rightChild->getBox())) {
      // Rz contains intersctn of z & rightChild box

      // test Rz and right child node
      Rtest = (getRightChild()->spContains(Rz));
      RtestSuccess = true;
    }

    // if both children tested
    if (LtestSuccess && RtestSuccess) {
      //return value is the result of both tests
        // if the same or BI_INDET if diff
      Ltest==Rtest ?
        retValue = Ltest : retValue=BI_INDET;
    }

    // if has two children but neither was tested
    // ie neither Intersection() returned true
    if (hasRCwithBox() && hasLCwithBox()
      && !LtestSuccess && !RtestSuccess) {
      retValue = BI_FALSE;
      // note that the AIA book has BI_TRUE here
      // but this can't be correct
    }

    // if has two children but only right was tested
    // ie left Intersection() returned false
    if (hasRCwithBox() && hasLCwithBox()
      && !LtestSuccess && RtestSuccess) {
      retValue = Rtest;
      // return value result of test of right side
    }

    // if has two children but only left was tested
    // ie right Intersection() returned false
    if (hasRCwithBox() && hasLCwithBox()
      && LtestSuccess && !RtestSuccess) {
      retValue = Ltest;
      // return value result of test of left side
    }

    // if has right child only and that child was tested
    // ie Intersection() returned true
    if (hasRCwithBox()
      && !hasLCwithBox() && RtestSuccess) {
      // if all of z contained in right child's box
      if (Rz==z) {
        retValue = Rtest;
      }
      // return false if Rtest false, else INDET
      else {
        Rtest==BI_FALSE ? retValue = BI_FALSE
          : retValue = BI_INDET;
      }
    }

    // if has right child only and that child not tested
    // ie Intersection() returned false
    if (hasRCwithBox()
      && !hasLCwithBox() && !RtestSuccess) {
      retValue = BI_FALSE;
    }

    // if has left child only and that child was tested
    // ie Intersection() returned true
    if (!hasRCwithBox() && hasLCwithBox()
      && LtestSuccess) {
      // if whole of z contained in left child's box
      if (Lz==z) {
        retValue = Ltest;
      }
      // return false if Ltest false, otherwise INDET
      else {
        Ltest==BI_FALSE ?
          retValue = BI_FALSE :
          retValue = BI_INDET;
      }
    }

    // if has left child only & that child was not tested
    // ie Intersection() returned false
    if (!hasRCwithBox() && hasLCwithBox()
      && !LtestSuccess) {
      retValue = BI_FALSE;
    }

    // case no children covered by isLeaf() block above

  } // end of (!isEmpty() && !isLeaf())

  // case of isEmpty() being true is take care of
  // by default return value being BI_FALSE

  return retValue;

} // end of spContains for ivector

BOOL_INTERVAL SPMinimalnode::spContains ( const rvector & p ) const [virtual]

Check if rvector p is contained in this node or any of its children.

Note that this checks not only the box represented by this node but the children as well. Returns a BOOL_INTERVAL type but this can actually only be BI_TRUE or BI_FALSE (not BI_INDET = indeterminate).

{
  // p is assumed not to be empty
  // nb Intersection() gives error if unequal index sets passed

  BOOL_INTERVAL retValue = BI_FALSE; // for the return value

  //cast p to an ivector
  ivector pvector = _ivector(p);

  // case of a non-empty leaf
  if (!isEmpty() && isLeaf()) {


    //find if p is in the box
    if (pvector <= getBox()) {
      retValue = BI_TRUE;
    }
    //else retValue keeps default value of BI_FALSE


  } // end (!isEmpty() && isLeaf())

  //case of an non-empty non-leaf
  if (!isEmpty() && !isLeaf()) {

    // to hold results of tests on left and right children
    BOOL_INTERVAL Ltest = BI_FALSE;
    BOOL_INTERVAL Rtest = BI_FALSE;

    // Find if there is a leftChild with a box
    if (hasLCwithBox()) {
      // test left child node
      Ltest = (getLeftChild()->spContains(p));
    }


    // Find if there is a rightChild with a box
    if (hasRCwithBox()) {
      // test Rz and right child node
      Rtest = (getRightChild()->spContains(p));
    }

    if ((Ltest==BI_TRUE) || (Rtest==BI_TRUE)) {
      retValue = BI_TRUE;
    }
    //else retValue keeps default value of BI_FALSE

    // case no children taken care of by isLeaf() above

  } // end of (!isEmpty() && !isLeaf())

  // case isEmpty() true covered by default retValue = BI_FALSE

  return retValue;

} // end of spContains for rvector

SPMinimalnode * SPMinimalnode::spLeafBoxDifference	(	const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return a tree representing difference between two subpavings.

The difference is the boxes covering space that is represented by spn1 but is not in the subpaving represented by spn2.

Parameters:

spn1	root of tree representing a subpaving.
spn2	root of tree representing another subpaving.

Returns:: a root of a tree representing a subpaving which is the space represented by spn1 that is not represented by spn2.

{
  SPMinimalnode* diffSP = NULL;
  
  try {
    BoxVec diffBoxes;
    diffBoxes = vecLeafBoxDifference(diffBoxes, spn1, spn2);
    if (!diffBoxes.empty()) {

      ImageList listBoxes;
      listBoxes.insert(listBoxes.end(), diffBoxes.begin(),
                        diffBoxes.end());
      ivector root = spn1->getBox();

      diffSP = makeTreeFromLeaves(root, listBoxes);

      if (diffSP != NULL) {
        diffSP->setNodeName("X");
        diffSP->recursiveRename();
      }
    }

    return diffSP;
  }
  catch(std::exception const& e) {
    delete diffSP;
    diffSP = NULL;
    throw;
  }
}

SPMinimalnode * SPMinimalnode::spLeafBoxIntersection	(	const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return subpaving representing intersection of two subpavings.

The intersection is the boxes covering space that that is represented by both trees.

Parameters:

spn1	root of tree representing a subpaving.
spn2	root of tree representing another subpaving.

Returns:: root of a tree whose leaves represent the boxes that cover space in common between both subpavings.

{
  SPMinimalnode* interSP = NULL;
  
  try {
    BoxVec interBoxes;
    interBoxes = vecLeafBoxIntersection(interBoxes,
            spn1, spn2);
    if (!interBoxes.empty()) {

      ImageList listBoxes;
      listBoxes.insert(listBoxes.end(), interBoxes.begin(),
                        interBoxes.end());
      ivector root = spn1->getBox();

      interSP = makeTreeFromLeaves(root, listBoxes);

      if (interSP != NULL) {
        interSP->setNodeName("X");
        interSP->recursiveRename();
      }
    }

    return interSP;
  }
  catch(std::exception const& e) {
    delete interSP;
    interSP = NULL;
    throw;
  }
  
}

SPMinimalnode * SPMinimalnode::spLeafBoxOuterJacket	(	const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return an SPMinimalnode tree representing the outer jacket of 2 subpavings.

The outer jacket tree is the nodes in common between two SPMinimalnode trees. i.e. the 'outer jacket' that fits both of the subpavings represented by the given trees.

Parameters:

spn1	root of tree representing a subpaving.
spn2	root of tree representing another subpaving.

Returns:: root of a tree whose leaves represent the boxes that cover both subpavings.

{
  SPMinimalnode* jacketSP = NULL;
  try {
    
    BoxVec jacketBoxes;
    jacketBoxes = vecLeafBoxOuterJacket(jacketBoxes,
            spn1, spn2);
    if (!jacketBoxes.empty()) {

      ImageList listBoxes;
      listBoxes.insert(listBoxes.end(), jacketBoxes.begin(),
                        jacketBoxes.end());
      ivector root = spn1->getBox();

      jacketSP = makeTreeFromLeaves(root, listBoxes);

      if (jacketSP != NULL) {
        jacketSP->setNodeName("X");
        jacketSP->recursiveRename();
      }

    }

    return jacketSP;
  }
  catch(std::exception const& e) {
    delete jacketSP;
    jacketSP = NULL;
    throw;
  }
}

BoxVec & SPMinimalnode::vecBoxNodeDifference	(	BoxVec &	boxes,
		ivector	box1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return boxes of space that is difference between box and subpaving.

The difference is the boxes covering space that is in box1 but is not in the subpaving represented by spn2.

Parameters:

boxes	is a reference to a container of boxes to be filled.
box1	a box.
spn2	root of tree representing a subpaving.

Returns:: boxes in box1 that is not in subpaving represented by spn2.

{
  if (spn2 == NULL) boxes.push_back(box1);

  else if (!(spn2->isLeaf())) {
    // bisect box1
    int maxdiamcomp = MaxDiamComp(box1);
    // new ivectors from splitting root along its biggest dimension
    ivector leftbox = Lower(box1, maxdiamcomp);
    ivector rightbox = Upper(box1, maxdiamcomp);
    boxes = vecBoxNodeDifference(boxes, leftbox, spn2->getLeftChild());
    boxes = vecBoxNodeDifference(boxes, rightbox, spn2->getRightChild());
  }
  // else spn2 must be a leaf so there is no difference

  return boxes;
}

BoxVec & SPMinimalnode::vecLeafBoxDifference	(	BoxVec &	boxes,
		const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return boxes of space that is the difference between two subpavings.

The difference is the boxes covering space that is represented by spn1 but is not in the subpaving represented by spn2.

Parameters:

boxes	is a reference to a container of boxes to be filled.
spn1	root of tree representing a subpaving.
spn2	root of tree representing another subpaving.

Returns:: boxes of space represented by spn1 that is not represented by spn2.

{
  if (spn1 != NULL && spn2 == NULL) {

    SPnodeConstPtrs leaves1;
    spn1->getConstSPnodeLeaves(leaves1);
    SPnodeConstPtrsItr it;
    for (it = leaves1.begin(); it < leaves1.end(); it++) {
      boxes.push_back((*it)->getBox());
    }
  }

  if (spn1 != NULL && spn2 != NULL
      && (spn1->getBox() == spn2->getBox())) {

    if (spn1->isLeaf() && !(spn2->isLeaf())) {
      // now we want to get any part of the box of spn1 that is
      // not represented by whatever boxes hang off spn2
      boxes = vecBoxNodeDifference(boxes, spn1->getBox(), spn2);
    }

    // if spn1 is not a leaf but spn2 is, then there is nothing
    // represented in spn1 that is not already represented in spn2

    if (!(spn1->isLeaf()) && !(spn2->isLeaf())) {
      // recurse on the children
      boxes = vecLeafBoxDifference(boxes, spn1->getLeftChild(),
            spn2->getLeftChild());
      boxes = vecLeafBoxDifference(boxes, spn1->getRightChild(),
            spn2->getRightChild());
    }
  }

  // if spn1 is null and spn2 is not null we don't do anything
  // if both not null but the boxes don't match we don't do anything
  return boxes;
}

BoxVec & SPMinimalnode::vecLeafBoxIntersection	(	BoxVec &	boxes,
		const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return container of boxes represented by intersection of 2 subpavings.

The intersection is the boxes covering space in the subpavings represented by both trees.

Parameters:

boxes	is a reference to a container of boxes to be filled.
spn1	root of tree representing a subpaving (can be NULL).
spn2	root of tree representing another subpaving (can be NULL).

Returns:: a container of boxes that is the intersection of the boxes represented by the leaves of spn1 and the boxes represented by the leaves ofspn2.

{
  // only do something if both nodes are non-null and boxes match
  if (spn1 != NULL && spn2 != NULL &&
          (spn1->getBox() == spn2-> getBox())) {

    // if both are leaves (and boxes match), push back the matching box
    if (spn1->isLeaf() && spn2->isLeaf()) boxes.push_back(spn1->getBox());

    // if one is a leaf and one is not, the children of the non-leaf
    // are all in the intersection
    if (!(spn1->isLeaf()) && spn2->isLeaf()) {
      SPnodeConstPtrs leaves1;
      spn1->getConstSPnodeLeaves(leaves1);
      SPnodeConstPtrsItr it;
      for (it = leaves1.begin(); it < leaves1.end(); it++) {
        boxes.push_back((*it)->getBox());
      }
    }

    if (spn1->isLeaf() && !(spn2->isLeaf())) {
      SPnodeConstPtrs leaves2;
      spn2->getConstSPnodeLeaves(leaves2);
      SPnodeConstPtrsItr it;
      for (it = leaves2.begin(); it < leaves2.end(); it++) {
        boxes.push_back((*it)->getBox());
      }
    }

    // if both have children, recurse on the children
    if (spn1->hasRCwithBox() && spn2->hasRCwithBox())
      boxes = vecLeafBoxIntersection(boxes, spn1->getRightChild(),
                          spn2->getRightChild());
    if (spn1->hasLCwithBox() && spn2->hasLCwithBox())
      boxes = vecLeafBoxIntersection(boxes, spn1->getLeftChild(),
                          spn2->getLeftChild());
  }

  return boxes;
}

BoxVec & SPMinimalnode::vecLeafBoxOuterJacket	(	BoxVec &	boxes,
		const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return container of boxes represented by commonality of 2 subpavings.

Finds the boxes represented by the deepest common level of nodes between two SPMinimalnode trees i.e. the 'outer jacket' that is the finest subpaving that fits around both of the subpavings represented by the given trees.

Parameters:

boxes	is a reference to a container of boxes to be filled.
spn1	root of tree representing a subpaving.
spn2	root of tree representing another subpaving.

Returns:: a container of boxes that is the outer jacket of spn1, spn2.

{
  // only do something if both nodes are non-null and boxes match
  if (spn1 != NULL && spn2 != NULL &&
          (spn1->getBox() == spn2-> getBox())) {

    // if both are leaves or
    // one of them does not have a child that the other has
    // then push back the box of the node we are in now
    if (spn1->isLeaf() && spn2->isLeaf()) {
      boxes.push_back(spn1->getBox());
    }
    else if ((spn1->getLeftChild() != NULL
          && spn2->getLeftChild() == NULL)
          || (spn1->getLeftChild() == NULL
          && spn2->getLeftChild() != NULL)
          || (spn1->getRightChild() != NULL
          && spn2->getRightChild() == NULL)
          || (spn1->getRightChild() == NULL
          && spn2->getRightChild() != NULL)) {
      boxes.push_back(spn1->getBox());
    }

    else {
      // we recurse on the children if both have both children
      if (spn1->getLeftChild() != NULL
            && spn2->getLeftChild() != NULL) {
        boxes = vecLeafBoxOuterJacket(boxes,
              spn1->getLeftChild(), spn2->getLeftChild());
      }
      if (spn1->getRightChild() != NULL
            && spn2->getRightChild() != NULL) {

        boxes = vecLeafBoxOuterJacket(boxes,
              spn1->getRightChild(), spn2->getRightChild());
      }
    }
  }
  return boxes;
}

double SPMinimalnode::volDifference	(	const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return the sum of the volume of the difference between 2 subpavings.

The difference is taken on leaf nodes using vecLeafBoxDifference.

Parameters:

spn1	root of tree representing a subpaving.
spn2	root of tree representing another subpaving.

Returns:: the total volume of the space represented by spn1 that is not represented by spn2.

{
  BoxVec diffBoxes;
  diffBoxes = vecLeafBoxDifference(diffBoxes,
          spn1, spn2);
  BoxVecItr bit;
  double diffVol = 0;
  for (bit = diffBoxes.begin(); bit < diffBoxes.end(); bit++) {
    diffVol += Volume (*bit);
  }
  return diffVol;
}

double SPMinimalnode::volIntersection	(	const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return the sum of the volume of intersection between two subpavings.

The intersection is taken on leaf nodes using vecLeafBoxIntersection.

Parameters:

spn1	first subpaving to intersect, can be NULL.
spn2	second subpaving to intersect, can be NULL.

Returns:: the total volume of the space in common between the two subpavings.

{
  BoxVec interBoxes;
  interBoxes = vecLeafBoxIntersection(interBoxes,
          spn1, spn2);
  BoxVecItr bit;
  double interVol = 0;
  for (bit = interBoxes.begin(); bit < interBoxes.end(); bit++) {
    interVol += Volume (*bit);
  }
  return interVol;
}

double SPMinimalnode::volOuterJacket	(	const SPMinimalnode *const	spn1,
		const SPMinimalnode *const	spn2
	)		`[static]`

Return the sum of the volume of outer jacket of two subpavings.

The outerjacket is found using vecLeafBoxOuterJacket.

Parameters:

spn1	root of tree representing a subpaving.
spn2	root of tree representing another subpaving.

Returns:: the volume of the smallest subpaving containing both subpavings.

{
  BoxVec jacketBoxes;
  jacketBoxes = vecLeafBoxOuterJacket(jacketBoxes,
          spn1, spn2);
  BoxVecItr bit;
  double jacketVol = 0;
  for (bit = jacketBoxes.begin(); bit < jacketBoxes.end(); bit++) {
    jacketVol += Volume (*bit);
  }
  return jacketVol;
}

SPMinimalnode * SPMinimalnode::vtkPaving ( const std::string filename ) [static]

Make a subpaving from vtk file data.

Expects a file of structured point vtk data, with 10 header lines, spacing on 4th line, and 255 signifying voxel in the image. Uses MakeTreeFromVoxels(...)

Parameters:

filename is the name of the file to get the vtk data from.

Returns:: a pointer to the root node of a new tree (can be null).

{
  SPMinimalnode* newTree = NULL;
  
  try {

    size_t expectedDims = 3;

    IntVec Xs;
    IntVec Ys;
    IntVec Zs;

    // get the spacing and fill in the coordinates vectors using
    // getCoordinatesFromVtk.
    // getCoordinatesFromVtk expects 10 header lines with spacings on 4th
    IntVec spacing = getCoordinatesFromVtk(Xs, Ys, Zs, filename);
    bool success = ((spacing.size() == expectedDims) && (spacing[0] > 0)
                && (spacing[0] == spacing[1])
                && (spacing[0] == spacing[2]));

    if (success) {

      ivector rootbox(expectedDims);

      double maxXYZ = spacing[0] * 1.0;

      ImageList boxes;

      double totalListVol = 0;

      IntVecItr xIt = Xs.begin();
      IntVecItr yIt = Ys.begin();
      IntVecItr zIt = Zs.begin();

      for (xIt = Xs.begin(); xIt < Xs.end(); xIt++, yIt++, zIt++) {
        ivector box(expectedDims);
        // make the box so that its boundaries are on the inner edges
        // of the voxel
        interval xdim(Sup(_interval(*xIt/maxXYZ)),
              Inf(_interval(*xIt + 1.0)/maxXYZ));
        interval ydim(Sup(_interval(*yIt/maxXYZ)),
              Inf(_interval(*yIt + 1.0)/maxXYZ));
        interval zdim(Sup(_interval(*zIt/maxXYZ)),
              Inf(_interval(*zIt + 1.0)/maxXYZ));
        box[1] = xdim;
        box[2] = ydim;
        box[3] = zdim;
        boxes.push_back(box);
        totalListVol += Volume(box);

      }

      rootbox[1] = interval(0.0, 1.0);
      rootbox[2] = interval(0.0, 1.0);
      rootbox[3] = interval(0.0, 1.0);


      newTree = makeTreeFromVoxels(rootbox, boxes,
                    maxXYZ, expectedDims);
    }

    if (newTree != NULL) {
      newTree->setNodeName("X");
      newTree->recursiveRename();
    }
  
    return newTree;
  }
  catch(std::exception const& e) {
    delete newTree;
    newTree = NULL;
    throw;
  }
  
}

Friends And Related Function Documentation

SPMinimalnode * ImageSp	(	PIVF	f,
		SPMinimalnode *	spn,
		double	eps
	)		`[related]`

Creation of image subpaving with Interval Analysis.

ImageSp uses Mince() to chop up spn and then Evaluate() and Regularize() to find a regular minimal subpaving covering the set of images of the boxes of the minced spn.

ImageSp is now a non-friend non-member function (compare to AIASPnode::ImageSp()) which now uses public member functions in the SPMinimalnode class.

Parameters:

f	a (*PIVF) which specifies the inclusion function of f and returns the inclusion function image [f][x] of an interval vector [x].
spn	the minimal subpaving for which we wish to find a subpaving covering the image under f.
eps	the precision with which the returned subpaving should be formed.

Returns:: a minimal regular subpaving covering the image of a subpaving under some function f.

SPMinimalnode * Sivia	(	PIBT	BoolTest,
		const SPMinimalnode *const	toInvert,
		SPMinimalnode *const	search,
		const double	eps
	)		`[related]`

Set Inversion Via Interval Analysis.

SIVIA progressively subdivides the boxes of the initial search subpaving and calls itself recursively to select or reject or retest the resulting subpavings until the desired level of precision, specified by eps, in forming the subpaving to be returned has been achieved.

Sivia is now a non-friend non-member function (compare to AIASPnode::Sivia()) which now uses public member functions in the SPMinimalnode class.

Parameters:

BoolTest	a (*PIBT)() which specifies the inclusion function of f and tests the inclusion function image [f][x] of an interval vector [x] for containment in an SPnode.
toInvert	the subpaving we are attempting to find the reciprocal image of, the SPMinimal passed to BoolTest.
search	a subpaving whose box forms the interval vector passed to BoolTest.
eps	the precision with which the returned subpaving should be formed.

Returns:: a minimal regular subpaving covering the reciprocal image of toInvert under some function f.

The documentation for this class was generated from the following files:

spminimalnode.hpp
spalgorithms.hpp
spminimalnode.cpp

Public Member Functions

Static Public Member Functions

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation