AIASubPaving node class. More...

Public Member Functions
	AIASPnode ()
	Default constructor.
	AIASPnode (ivector &v)
	Initialized constructor.
	AIASPnode (const AIASPnode &n)
	Copy constructor.
	~AIASPnode ()
	Destructor.
Friends
Friend functions
We have followed the implementation in [AIA2001, p. 336-348], which uses friend functions in order to give non-member functions access to the private data members of the class.
ivector	Box (AIASubPaving a)
	Returns a copy of theBox of an AIASubPaving. */.
bool	IsEmpty (AIASubPaving a)
	Check if the AIASubPaving is empty.
bool	IsLeaf (AIASubPaving a)
	Check if the AIASubPaving is a leaf.
double	Volume (AIASubPaving a)
	Volume of an AIASubPaving.
int	NbLeaves (AIASubPaving a)
	Number of leaves of an AIASubPaving.
AIA_BOOL_INTERVAL	operator<= (const ivector &, AIASubPaving)
	Check for containment of interval vector or box in the AIASubPaving.
std::ostream &	operator<< (std::ostream &, AIASubPaving)
	Output the contents of an AIASubPaving.
AIASubPaving	Sivia (AIA_PIBT BoolTest, AIASubPaving A, double)
	Set Inversion Via Interval Analysis method taken from AIA2001.
void	Expand (AIASubPaving A, int comp)
	Expand a leaf node to have two child nodes.
AIASubPaving	ReUnite (AIASubPaving lChild, AIASubPaving rChild, ivector x)
	Return a minimal subpaving from two sibling subpavings.
void	Mince (AIASubPaving A, double eps)
	Mince up a subpaving.
void	Evaluate (AIA_PIVF, AIASubPaving A, std::list< ivector > &evalImages, ivector &hull)
	Evaluate the image.
AIASubPaving	Regularize (ivector &hull, std::list< ivector > &ivectorList, double eps)
	Forms a minimal image subpaving from a list of interval vector images.
AIASubPaving	ImageSp (AIA_PIVF, AIASubPaving A, double eps)
	Creation of an image subpaving (ImageSp) with Interval Analysis from AIA2001.
Related Functions
(Note that these are not member functions.)
bool	volCompare (const ivector &a, const ivector &b)
	Compare volumes of two boxes.

Detailed Description

AIASubPaving node class.

A class based on the Sub-paving node class from [AIA2001, p. 336-348] implemented over C-XSC. AIASPnode is a node in the tree representation of a regular subpaving. A node represents a box (interval vector). SPnodes are linked to children to form a binary tree. A subpaving of [x] (union of non-overlapping subboxes of [x]) is represented by the leaves (degenerate/ child-less) nodes in the tree. This class replicates the set computation functionality of the subpaving nodes developed in AIA2001.

Friends And Related Function Documentation

void Evaluate	(	AIA_PIVF	f,
		AIASubPaving	A,
		std::list< ivector > &	evalImages,
		ivector &	hull
	)		`[friend]`

Evaluate the image.

Parameters:

f	a pointer to an interval vector function which returns the image box under f of some interval vector
A	the node of the subpaving to be evaluated
evalImages	a container of image interval vectors
hull	the interval hull of the image interval vectors Fills in the list of images using f of the subpaving boxes and update the hull of all the images.

Function to evaluate all the boxes in AIASubPaving. The images of all the boxes are formed and put into a list and the interval hull of the union of all the boxes is formed. Interval hull of a union is implemented under cxsc with | operator. Boxes are expected to have been created by Mince(). The argument f is a pointer to an interval vector function AIA_PIVF (which returns an interval vector). AIASubPaving A is the AIASubPaving to be evaluated (should be const - it is not changed in this function). evalImages is the current list of images to be added to in the function call, hull is an ivector hull of images currently in the list which may be altered in this call if an image is added to list

{
  if (A!=NULL && IsLeaf(A))
  {
    // make an ivector image using the AIA_PIVF function f on Box(A)
    ivector image = f(Box(A));

    // if no images in image set yet, make hull the image
    if (evalImages.size() == 0) hull = image;
    // if there are images in the image set, hull is the convex hull of
    else hull = (hull | image);
    // the current hull and the ivector image from f(Box(A))

    // add the image to the list of images
    evalImages.push_back(image);

  }                 // end of is a leaf

  // if not a leaf, recursively call Evaluate on children
  if (A!=NULL && !IsLeaf(A))
  {

    Evaluate(f, A->leftChild, evalImages, hull);
    Evaluate(f, A->rightChild, evalImages, hull);

  }                 // end of if is not a leaf

  // case where A == NULL does nothing, just returns
  return;
}

void Expand	(	AIASubPaving	A,
		int	comp
	)		`[friend]`

Expand a leaf node to have two child nodes.

Parameters:

A	a pointer to the node to be expanded.
comp	is the dimension to split along.

{
  // comp argument is passed to Upper() and Lower()
  // these functions split the box normal to direction set by comp

  if (!IsLeaf(A)) return;
  ivector lC,rC;
  Lower(Box(A),lC,comp); Upper(Box(A), rC, comp);
  A->leftChild = new AIASPnode(lC);
  A->rightChild = new AIASPnode(rC);
  //A->leftChild = new AIASPnode(Lower(Box(A),comp));
  //A->rightChild = new AIASPnode(Upper(Box(A),comp));
}

AIASubPaving ImageSp	(	AIA_PIVF	f,
		AIASubPaving	A,
		double	eps
	)		`[friend]`

Creation of an image subpaving (ImageSp) with Interval Analysis from AIA2001.

Returns:: a minimal regular subpaving coveringing the image of A under some function f

Parameters:

f	a (*AIA_PIVF) which specifies the inclusion function of f and returns the inclusion function image [f][x] of an interval vector [x]
A	the 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 ImageSp uses Mince() to chop up A and then Evaluate() and Regularize() to find a regular minimal subpaving covering the set of images of the boxes of the minced A.

{
  list<ivector> images;
  ivector hull;

  Mince(A, eps);

  //cout << "After mince " << endl;
  //cout << "A has volume  " << Volume (A) << " and number of leaves "
  //  << NbLeaves(A) << endl;

  Evaluate(f, A, images, hull);

  //cout << "After evaluate " << endl;
  //cout << "Size of image list is : " << images.size()
  //  << "  and hull has volume " << Volume(hull) << endl;

  /* the output of eval is not included in the AIA examples, but it makes
  an interesting comparison to the final subpaving */
  // Filename
  ofstream os2("eval.txt");
  list<ivector>::iterator it;
  for (it=images.begin(); it!=images.end(); it++)
  {
    ivector box = *it;
    os2 << "[ " << Inf(box[1]) << " , " << Sup(box[1]) << " ] , [ "
      << Inf(box[2]) << " , " << Sup(box[2]) << " ]" <<  endl;
  }
  // end of difference from AIA examples

  return (Regularize(hull, images, eps));

}

void Mince	(	AIASubPaving	A,
		double	eps
	)		`[friend]`

Mince up a subpaving.

Parameters:

A	a pointer to the node whose box is to be minced
eps	the maximum diameter any box in the subpaving should be Mince minces recursively until each leaf has maximum diameter smaller than eps.

Mince transforms a minimal AIASubPaving into a non-minimal AIASubPaving, ie may have sibling leaves. Any leaf AIASubPaving with a box with diameter greater than eps will be expanded. Mince will keep mincing until every leaf AIASubPaving has a box with diameter < eps

{
  if (IsEmpty(A)) return;

  if (IsLeaf(A))
  {
    int comp;       // value is given by calling MaxDiam function below

    // if leaf and box smaller than eps then return
    if(MaxDiam(Box(A),comp)<eps) return;

    // if leaf and box not smaller than eps then expand
    Expand(A,comp);

  }                 // end if a leaf

  // not a leaf, recurse Mince() on left and right children
  Mince(A->rightChild,eps);
  Mince(A->leftChild,eps);

}

std::ostream& operator<<	(	std::ostream &	os,
		AIASubPaving	a
	)		`[friend]`

Output the contents of an AIASubPaving.

This output format is not the same as used in the example code provided for [AIA2001], but is adapted for easy reading and rendering in Matlab.

{
  if (a==NULL) return os;

  //if (IsLeaf(a)) os << (*(a->theBox)) << std::endl;
  //output for Jenny's matlab format, dimension = 2 max
  if (IsLeaf(a))
  {
    ivector x = *(a->theBox);
    os << "[ " << Inf(x[1]) << " , " << Sup(x[1]) << " ] , "
      << "[ " << Inf(x[2]) << " , " << Sup(x[2]) << " ]"   << std::endl;
  }
  else
    { os << (a->leftChild); os << (a->rightChild); }

    return os;
}

AIASubPaving Regularize	(	ivector &	hull,
		std::list< ivector > &	ivectorList,
		double	eps
	)		`[friend]`

Forms a minimal image subpaving from a list of interval vector images.

Uses Reunite() and recursive calls to Regularize() to work up from leaf nodes to form a minimal subpaving

Returns:: a regular mimimal subpaving with root box hull

Parameters:

hull	the interval hull of all the interval vectors in the image list
ivectorList	a collection of possibly overlapping interval vectors to be made into a regular subpaving
eps	the precision with which the returned subpaving should be formed There are some minor changes in this function compared to the implementation in AIA2001, p. 346. We use the std::list to store the interval vector images instead of a [constantly sorted] set. We sort the list, using volCompare(), only when we need to. We sort smallest to largest (the natural std::list sort order) (the Jaulin et al images are sorted largest to smallest) and hence we find the largest image box at the end of the the list rather than at the start.

Regularize creates an AIASubPaving from all the ivectors in the ivectorList. The root of the AIASubPaving will have Box = hull where hull has already been formed from the union of all the ivectors in the ivectorList. Regularize is applied recursively on bisected half of hull and new lists until either there are no images in the list or the diameter of the hull is below eps.

{
                    // return NULL if the list is empty
  if (ivectorList.size()==0) return NULL;

  // sort the list
  // Jaulin et al do not have this step because they have their own IMAGELIST
  // class which acts like a set and keeps the contents in order.  But we are
  // using the stl std::list and so it is unsorted when it is passed to
  // Regularize.  It is more effient to sort it once per call to Regularise
  // than to keep it sorted as it is being built because the sorted order is
  // only needed when the entire list has been built

  // sort using the volCompare function
  ivectorList.sort(volCompare);
  // this sorts smallest to largest (the opposite to Jaulin et al)

  // if the hull is equal to the last (largest) box in the list,
  // this becomes the AIASubPaving
  if (hull==(*ivectorList.rbegin())) return new AIASPnode(hull);

  // un-valued int to take value for larged dimension calculated from MaxDiam
  int maxdiamcomp;

  //if the current maximum diameter is < eps return a new AIASubPaving from hull
  if (MaxDiam(hull,maxdiamcomp)<eps) return new AIASPnode(hull);

  // new ivectors from splitting hull in its biggest dimension
  ivector lefthull = Lower(hull,maxdiamcomp);
  ivector righthull = Upper(hull,maxdiamcomp);

  // create two empty lists
  list<ivector> leftlist,rightlist;

  // iterator to for the list
  list<ivector>::iterator it;

  // iterate through the current list and put the intersection of any element
  // with the lefthull into the new left list, and the intersection of any
  // element with new right hull into the new rightlist.
  for (it=ivectorList.begin(); it!=ivectorList.end(); it++)
  {
    // temporary variables to take the results of call in Intersect
    ivector interLeft, interRight;

    if (Intersection(interLeft, *it, lefthull))
    {
      leftlist.push_back(interLeft);
    }

    if (Intersection(interRight, *it, righthull))
    {
      rightlist.push_back(interRight);
    }

  }  // end of iteration through list elements

  // recursively call Regularize with lefthull, leftlist, righthull, rightlist
  // reunite the results using hull as the box for the parent node
  // Regularize creates a minimal AIASubPaving (no sibling child nodes)
  return ReUnite(Regularize(lefthull,leftlist,eps),
    Regularize(righthull,rightlist,eps),hull);
}

AIASubPaving ReUnite	(	AIASubPaving	lChild,
		AIASubPaving	rChild,
		ivector	x
	)		`[friend]`

Return a minimal subpaving from two sibling subpavings.

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

Returns:: a minimal subpaving from two sibling subpavings

Parameters:

lChild	a pointer to the leftChild node to be reunited
rChild	a pointer to the rightChild node to be reunited
x	is the box of the new subpaving to be returned

{
  if(IsEmpty(lChild)&&IsEmpty(rChild)) return NULL;
  AIASubPaving result = new AIASPnode(x);
  // both AIASubPavings are leaves so discard them: new AIASubPaving is a leaf
  if( IsLeaf(lChild)
    &&IsLeaf(rChild)
    &&(  x == ( Box(lChild) | Box(rChild) )  )
    )
    { delete lChild; delete rChild; return result; }

    // if there are not two non-null potential children
    // (so presumably just one child), just graft it on
    // similarly if at least one child is not a leaf, just graft the potential
    // children on
    result->leftChild = lChild; result->rightChild = rChild;

  return result;
}

AIASubPaving Sivia	(	AIA_PIBT	BoolTest,
		AIASubPaving	A,
		double	eps
	)		`[friend]`

Set Inversion Via Interval Analysis method taken from AIA2001.

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

Parameters:

BoolTest	a (*AIA_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. In this implementation, the body of BoolTest specifies both the subpaving we want the image of and the function f forming the image
A	a subpaving whose box forms the interval vector passed to BoolTest
eps	the precision with which the returned subpaving should be formed 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.

Set Inversion Via Interval Analysis method taken from AIA2001. Sivia gives an AIASubPaving which is based on the reciprocal image X of some function. Note that in this implementation, we get the outer AIASubPaving of two, (lowerX and UpperX) such that lowerX is in X is in upperX. The AIA_PIBT points to a function which specifies the function for which we want the reciprocal image and the AIASubPaving Y which should contain the reciprocal image. The AIA_PIBT function evaluates whether the image of some box (ivector) is in Y. The AIA_PIBT can return BI_TRUE, BI_FALSE, or BI_INDET (box partly in Y but not totally). If the AIASubPaving box tests BI_INDET and the box diameter is sufficiently small then it is given the benefit of the doubt and included in upperX. Otherwise if the AIA_PIBT function returns BI_INDET then the AIASubPaving is expanded, ie two AIASubPaving children created, and these AIASubPaving children are then tested. The argument A is an AIASubPaving. On the first pass through SIVIA, A should have a box which is guaranteed to contain upperX; this AIASubPaving is progressively refined. The argument eps specifies the 'sufficiently small' width for a box to be included in upperX...

{
  if (A==NULL) return NULL;

                    // test the box of the given AIASubPaving
  AIA_BOOL_INTERVAL test = BoolTest(Box(A));
  // Test function (may be passed as parameter to Sivia)

  // maxdiamcomp will be given a value by call to MaxDiam() below
  int maxdiamcomp;

  // the box fails the test
  if ( test==BI_FALSE ) return NULL;

  // if the box passes or the result is BI_INDET but the maximum diameter of
  // the box is small enough, then return a new AIASubPaving which is a copy of
  // the current one, ie include this AIASubPaving in outerX, our approximation
  // of X the reciprocal image
  if (test==BI_TRUE || MaxDiam(Box(A),maxdiamcomp)<eps)
    return new AIASPnode(*A);

  // SIVIA will only reach this point if the result of the test was BI_INDET
  // and the maximum diameter of the box is not small enough for the box to be
  // in outerX -- in this case we expand the AIASubPaving by giving it child
  // nodes and test them
  if (IsLeaf(A)) Expand(A,maxdiamcomp);

  // ReUnite is used to get a minimal AIASubPaving from merging two
  // AIASubPavings.  So will ensure that the AIASubPaving we return from Sivia
  // is minimal, ie will not have sibling leaves
  return ReUnite( Sivia(BoolTest,A->leftChild,eps),
    Sivia(BoolTest,A->rightChild,eps),
    Box(A));

}

bool volCompare	(	const ivector &	a,
		const ivector &	b
	)		`[related]`

Compare volumes of two boxes.

A function for comparing ivectors based on volume. Used in sorting a list of ivectors ordered by volume. Will abort if the index sets of the two ivectors are different sizes. Uses Volume() as defined in toolz.hpp

Returns:: TRUE if the Volume of a is strictly less than Volume of b

{
  bool returnValue = 0;

  // Make sure the vectors have the same number of elements and at
  // least one element each
  if( (Ub(a) - Lb(a)) == (Ub(b) - Lb(b)) && (Ub(a) - Lb(a))>=1 )
  {

                    // compare the two volumes
    returnValue = ((Volume(a)<Volume(b)));

  }
  else
  {
    std::cout
      << "Error in volCompare : comparing ivectors of different dimensions"
      << std::endl;
  }

  return returnValue;
}

double Volume ( AIASubPaving a ) [friend]

Volume of an AIASubPaving.

Sums the volumes of the leaves of the AIASubPaving.

{

  if (IsEmpty(a)) return 0.0;
  if (IsLeaf(a))
  {

                    // using Volume taking ivector argument
    return Volume(Box(a));
  }
  double vol=0.0;

  vol += Volume(a->leftChild);
  vol += Volume(a->rightChild);

  return (vol);
}

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

AIAsubpaving.hpp
AIAsubpaving.cpp

Public Member Functions

Friends

Related Functions

Detailed Description

Friends And Related Function Documentation