Tree: Exported struct. More...

#include <Tree.h>

Collaboration diagram for TreeStruct:

Classes
class	iterator
	A iterator class fore TreeStruct that allows for movement through the tree without changing anything in the tree itself. More...

Public Member Functions
	TreeStruct (Point *xp, unsigned long Npoints, short my_median_cut=1, PosType buffer=0.0)
	Build a complete tree from a list of points.

	TreeStruct (Point *xp, unsigned long npoints, PosType boundary_p1[2], PosType boundary_p2[2], PosType center[2], int Nbucket)
	Make a new tree and the linked list of points in it. Does not build the tree structure. The other constructor should be used to build the whole tree.

	~TreeStruct ()
	Free tree and the linked list of points in it.

TreeStruct::iterator	begin () const

TreeStruct::iterator	end () const

Branch *	getTop ()
	root branch

void	FindAllBoxNeighborsKist (Point point, Kist< Point > neighbors) const
	Finds all the leaves that are neighboring a point.

void	FindAllBoxNeighborsKist (Point point, std::vector< Point > &neighbors) const
	Finds all the leaves that are neighboring a point.

void	PointsWithinEllipKist (const PosType center, float rmax, float rmin, float posangle, Kist< Point > neighborkist) const
	Finds points within an ellipse.

PosType	PointsWithinKist (const PosType center, PosType rmax, Kist< Point > neighborkist, short markpoints) const
	Finds all points in tree that lie within rmax of the point ray[].

void	PointsWithinKist_iter (const PosType center, float rmin, float rmax, Kist< Point > neighborkist) const
	Finds all points within a circle. Much simpler, iterative algorithm.

Point *	NearestNeighborKist (const PosType center, int Nneighbors, Kist< Point > neighborkist) const
	Finds nearest neighbor points to ray.

bool	AtEdge (Point *point)
	true is point is on the edge of the field

bool	Test ()

Point *	RemoveLeafFromTree (TreeStruct::iterator &current, unsigned long *Npoints)
	Prune off points that are below a resolution and in an annulus on the source plane.

void	FillTree (Point *xp, unsigned long Npoints)
	Fill a tree with points. The previous tree structure will be destroyed. Used for refilling.

int	AddPointsToTree (Point *xpoint, unsigned long Nadd)
	Expands tree by adding points.

short	emptyTree ()
	Spawn a subtree with current as its top.

bool	isEmpty ()

unsigned long	getNbranches ()

void	printTree (TreeStruct::iterator &current)

void	checkTree ()

Point *	FindBoxPoint (const PosType *ray) const

void	_FindLeaf (TreeStruct::iterator &current, const PosType *ray, unsigned long Nadd=0) const

Public Attributes
PointList	pointlist
	list of points

Static Public Attributes
static std::mutex	mutex

Detailed Description

Tree: Exported struct.

Constructor & Destructor Documentation

◆ TreeStruct() [1/2]

TreeStruct::TreeStruct	(	Point *	xp,
		unsigned long	Npoints,
		short	my_median_cut = 1,
		PosType	buffer = 0.0 )

Build a complete tree from a list of points.

median_cut determines how the cells are subdivided if ==0 equal volume cuts, Warning this option causes an error if ==1 pseudo-median point cuts, never cuts through a point, but near the median < >

◆ TreeStruct() [2/2]

TreeStruct::TreeStruct	(	Point *	xp,
		unsigned long	npoints,
		PosType	boundary_p1[2],
		PosType	boundary_p2[2],
		PosType	center[2],
		int	my_Nbucket )

Make a new tree and the linked list of points in it. Does not build the tree structure. The other constructor should be used to build the whole tree.

Parameters

xp	array of points to be added to the tree
npoints	number of points
boundary_p1	bottom left hand corner of root
boundary_p2	upper right hand corner of root
center	center of root (this could be the center of mass)
my_Nbucket	maximum number of points allowed in a leaf

Member Function Documentation

◆ _FindLeaf()

void TreeStruct::_FindLeaf	(	TreeStruct::iterator &	current,
		const PosType *	ray,
		unsigned long	Nadd = 0 ) const

Finds the leaf the ray is in and adds Nadd to all of is parent leaves

◆ emptyTree()

short TreeStruct::emptyTree ( )

Spawn a subtree with current as its top.

The new tree contains all of the tree below the current. Warning:: Adding points to the new tree will not update the parent tree so it can become dangerously out of sync.

Empty tree of all point leaving a tree with an empty root.

The points are not freed, and the list structure is not destroyed.

FillTree can then be used to regenerate tree.

◆ FindAllBoxNeighborsKist() [1/2]

void TreeStruct::FindAllBoxNeighborsKist	(	Point *	point,
		Kist< Point > *	neighbors ) const

Finds all the leaves that are neighboring a point.

Points outside of grid have no box neighbors Warning: Does not take empty leaves into account.

◆ FindAllBoxNeighborsKist() [2/2]

void TreeStruct::FindAllBoxNeighborsKist	(	Point *	point,
		std::vector< Point * > &	neighbors ) const

Finds all the leaves that are neighboring a point.

Points outside of grid have no box neighbors Warning: Does not take empty leaves into account.

◆ FindBoxPoint()

Point * TreeStruct::FindBoxPoint ( const PosType * ray ) const

return a pointer to the point that is in the same box as ray[2] if Nbuck > 1 the head of the point array is returned

Memory

◆ NearestNeighborKist()

Point * TreeStruct::NearestNeighborKist	(	const PosType *	center,
		int	Nneighbors,
		Kist< Point > *	neighborkist ) const

Finds nearest neighbor points to ray.

This is a kludge that relies on NearestNeighbor which uses a List and translates the list to a kist. Could be rewritten.

Warning: The number of neighbor points in neighborkist will be less than Nneighbors when the number of points in the tree is less than Nneighbors

◆ PointsWithinEllipKist()

void TreeStruct::PointsWithinEllipKist	(	const PosType *	center,
		float	rmax,
		float	rmin,
		float	posangle,
		Kist< Point > *	neighborkist ) const

Finds points within an ellipse.

This becomes less efficient when the ellipse is very elongated. Could be improved by incorporating the test of it being in the ellipse into the tree walk.

The

Parameters

center	center of ellipse
rmax	major axis
rmin	minor axis
posangle	position angle of major axis, smallest angle between the x-axis and the long axis
neighborkist	output neighbor kist, will be emptied if it contains anything on entry

◆ PointsWithinKist()

PosType TreeStruct::PointsWithinKist	(	const PosType *	center,
		PosType	rmax,
		Kist< Point > *	neighborkist,
		short	markpoints ) const

Finds all points in tree that lie within rmax of the point ray[].

markpoints = 0 does not change in_image variable in any point, gives a list of neighbors = 1 makes in_image=YES for all points and their images in image, gives no list of neighbors = -1 makes in_image=NO for all points in image to reset, gives no list of neighbors

Returns the largest gridsize of the points within the circle. Note that this is the gridsize stored in the point. If finding points on the source plane the i_point->gridsize must be set to the same as the image point to get the largest gridsize on the image plane.

Parameters

center	center of circle
rmax	radius of circle
neighborkist	output neighbor kist, will be emptied if it contains anything on entry
markpoints	see comment

◆ RemoveLeafFromTree()

Point * TreeStruct::RemoveLeafFromTree	(	TreeStruct::iterator &	current,
		unsigned long *	Npoints )

Prune off points that are below a resolution and in an annulus on the source plane.

\brief THIS DOES NOT WORK YET!!!

Reduces the size of the tree by removing points and branches that are no longer needed.

unsigned long Grid::PruneTrees( PosType resolution /// Maximum size of a cell to be removed. ,bool useSB /// If true it will not remove any point that has a flux above fluxlimit. ,PosType fluxlimit /// flux limit threshold ){

long i,Ntmp,count = 0; PosType res,initres; bool go;

assert(trashkist);

if(i_tree == NULL) return 0; if(s_tree == NULL) return 0;

Ntmp = i_tree->pointlist.size();

i_tree->moveTop();

TreeStruct::iterator i_tree_current(i_tree); PointList::iterator i_tree_pointlist_current;

initres = (i_tree->getTop()->boundary_p2[0]-i_tree->getTop()->boundary_p1[0]); if(resolution > initres/3 || resolution <= 0.0) return 0; // do not allow pruning up to the initial grid size

walk tree i=0; go = true; do{ assert((*i_tree_current)->points->next || (*i_tree_current)->points->prev);

res = ((*i_tree_current)->boundary_p2[0]-(*i_tree_current)->boundary_p1[0]); if( (res <= resolution && i_tree_current.IsSquareBranch() ) && (*i_tree_current)->refined){

if(useSB){ go = true; Check if surface brightness of all points in cell are zero. i_tree_pointlist_current = (*i_tree_current)->points; for(i=0; i < (*i_tree_current)->npoints;++i,–i_tree_pointlist_current ){ if((*i_tree_pointlist_current)->surface_brightness*pow((*i_tree_pointlist_current)->gridsize,2) > fluxlimit ){ go = false; break; } } }

remove all lower branches and make current a leaf if(go && (*i_tree_current)->npoints > 1){

count += FreeBranchesBelow(i_tree_current,i_tree,s_tree,trashkist); } } }while(i_tree_current.TreeWalkStep(true));

rebuild source tree from list. if(count > 0) RebuildTreeFromList(s_tree);

assert(count == (Ntmp - i_tree->pointlist.size()) );

return count; }

Used to keep the number of grid points limited while telescoping.

The points that are removed have cells that do not overlap the inner circle and centers that are within the outer circle. Thus some points will be outside of the inner circle and some cells that are not removed may intersect with the outer circle.

unsigned long Grid::PrunePointsOutside( PosType resolution /// Maximum size of a cell to be removed. ,PosType *y /// Center on source plane ,PosType r_in /// Inner radius of annulus on the source plane ,PosType r_out /// Outer radius of annulus on the source plane ){

if(i_tree == NULL) return 0; if(s_tree == NULL) return 0; if(r_in > r_out || resolution <= 0) return 0; if(r_out <= 0.0) return 0.0;

PosType res,dr2;

long i,count = 0; Point *point; Branch *branch; Kist<Point> * subkist = new Kist<Point>; bool go = true; unsigned long Ntmp; Unit *unit;

assert(trashkist);

Make a kist of all points in the annulus. PointsWithinKist(s_tree,y,r_out+resolution,subkist,0); s_tree->PointsWithinKist_iter(y,r_in,r_out+resolution,subkist);

std::printf("number of points after PointsWithin %li\n",subkist->Nunits());

if(r_in > 0){ take out points that are within inner circle subkist->MoveToTop(); Ntmp = subkist->Nunits(); for(i=0;i<Ntmp;++i){ go = true; point = subkist->getCurrent(); if(point->gridsize*Ngrid_block > resolution){ if(subkist->AtTop()) go = false; subkist->TakeOutCurrent(); }else if( Utilities::cutbox(y,point->leaf->boundary_p1,point->leaf->boundary_p2,r_in) ){ if(subkist->AtTop()) go = false; subkist->TakeOutCurrent(); }

if(go) subkist->Down(); } } std::printf("number of points after culling %li\n",subkist->Nunits());

if(subkist->Nunits() == 0){ delete subkist; return 0; }

move from source plane to image plane subkist->TranformPlanes();

 TreeStruct::iterator i_tree_current(i_tree);

Take out all points that are not at the center of their parent refined cell subkist->MoveToTop(); Ntmp = subkist->Nunits(); for(i = 0; i < Ntmp ; ++i){ go = true; point = subkist->getCurrent(); i_tree_current = point->leaf; Move up to nearest ancestor that was refined. while(!((*i_tree_current)->refined) && i_tree_current.up() );

res = ((*i_tree_current)->boundary_p2[0]-(*i_tree_current)->boundary_p1[0]);

if((*i_tree_current)->npoints != Ngrid_block*Ngrid_block || res > resolution){ Take out the point if it is not in a parent block that has been refined than once or if the parent block is about the resolution limit if(subkist->AtTop()) go = false; subkist->TakeOutCurrent(); }else{ assert(inbox(point->x,(*i_tree_current)->boundary_p1,(*i_tree_current)->boundary_p2));

assert(fabs((*i_tree_current)->center[0] - ((*i_tree_current)->boundary_p2[0]+(*i_tree_current)->boundary_p1[0])/2) < point->gridsize/2); assert(fabs((*i_tree_current)->center[1] - ((*i_tree_current)->boundary_p2[1]+(*i_tree_current)->boundary_p1[1])/2) < point->gridsize/2 ); assert(point->gridsize < fabs((*i_tree_current)->boundary_p2[0]-(*i_tree_current)->boundary_p1[0]) ); assert(point->gridsize < fabs((*i_tree_current)->boundary_p2[1]-(*i_tree_current)->boundary_p1[1]) );

if( (point->gridsize)/2 < fabs(point->x[0] - (*i_tree_current)->center[0]) || (point->gridsize)/2 < fabs(point->x[1] - (*i_tree_current)->center[1]) ){ // Take out point if it is not at the center of it's parent block if(subkist->AtTop()) go = false; subkist->TakeOutCurrent(); } }

if(go) subkist->Down(); }

assert(subkist->AtBottom());

subkist->MoveToTop(); PointList::iterator i_tree_pointlist_current; while(subkist->Nunits() > 0){ i_tree_current = subkist->getCurrent()->leaf; Move up to nearest ancestor that was refined. while(!((*i_tree_current)->refined) && i_tree_current.up() );

assert((*i_tree_current)->npoints == Ngrid_block*Ngrid_block);

make sure that none of the child points are outside the annulus i_tree_pointlist_current = (*i_tree_current)->points; for(i=0;i < Ngrid_block*Ngrid_block ; ++i,–i_tree_pointlist_current){ dr2 = pow((*i_tree_pointlist_current)->image->x[0] - y[0],2) + pow((*i_tree_pointlist_current)->image->x[1] - y[1],2); if(dr2 > r_out*r_out || dr2 < r_in*r_in) break; if(dr2 < r_in*r_in) break; }

if(i == Ngrid_block*Ngrid_block){ branch = *i_tree_current;

count += FreeBranchesBelow(i_tree_current,i_tree,s_tree,trashkist);

assert((*i_tree_current)->npoints == 1); assert( fabs( 1 - ((*i_tree_current)->boundary_p2[0] - (*i_tree_current)->boundary_p1[0])/(*i_tree_current)->points->gridsize) < 1.0e-4 ); assert((*i_tree_current)->refined == false);

}

subkist->TakeOutCurrent();

}

delete subkist;

return count; }

\brief Empty trash points.

Frees point arrays whose heads are stored in trashlist.
If check=true it will only free arrays where all the points have NULL leafs.
   check=false all the point arrays are freed..

void CollectTrash(Kist<Point> * trashkist,bool check){ bool go; unsigned long i,j,Ntmp; Point *points;

if(trashkist->Nunits() == 0) return;

Ntmp = trashkist->Nunits(); for(j=0,trashkist->MoveToTop();j<Ntmp;++j){

if(!(trashkist->getCurrent()->head)){ // point is not the head of an array if(trashkist->AtTop()) go = false; else go = true; trashkist->TakeOutCurrent(); }else{

check to see if all points in the block have been removed from the trees if(check){ for(i=0;i<trashkist->getCurrent()->head;++i) if(trashkist->getCurrent()[i].leaf != NULL) break; }else{ i = trashkist->getCurrent()->head; }

if(i == trashkist->getCurrent()->head){ if(trashkist->AtTop()) go = false; else go = true; points = trashkist->TakeOutCurrent(); FreePointArray(points); }else{ go = true; } }

if(go) trashkist->Down(); }

return; }

Frees all branches of the tree below the current branch in i_tree if that branch is square and i_tree->current->refined == true. If either of these are not true nothing happens.

On exit: The i_tree->current is back to the original current. If it is square it will have no children and contain one point. The source points and branches are also removed.

unsigned long FreeBranchesBelow(TreeStruct::iterator &i_tree_current,TreeHndl i_tree,TreeHndl s_tree,Kist<Point> * trashkist){

if(!i_tree_current.IsSquareBranch()) return 0; if(i_tree_current.atLeaf()) return 0; if((*i_tree_current)->refined == false) return 0;

TreeStruct::iterator s_tree_current(s_tree); assert( s_tree !=NULL);

Branch *branch,*headbranch; Point *point; unsigned long Ntmp,NtoRemove,i,count = 0,count2 = 0,count1; PosType center[2]; PointList::iterator i_tree_pointlist_current; PointList::iterator s_tree_pointlist_current;

_freeBranches_iter(s_tree); // s_tree will no longer be valid on exit. This is to make sure it isn't used later without a rebuild.

headbranch = *i_tree_current; i_tree->TreeWalkStep(true);

while( (headbranch->child1 != NULL) || (headbranch->child2 != NULL) ){

assert(boxinbox(*i_tree_current,headbranch)); if(i_tree_current.atLeaf()){ assert(i_tree->current->points->image->leaf); s_tree->current = i_tree->current->points->image->leaf; // set s_tree to source of current image cell

branch = (*i_tree_current)->prev; i = branch->npoints;

if((*i_tree_current) != headbranch) i_tree->RemoveLeafFromTree(i_tree_current,&Ntmp);

                 test line  **************************

assert(*i_tree_current == branch); assert(i == (*i_tree_current)->npoints);

                 test line  **************************

assert((*i_tree_current)->points->next || (*i_tree_current)->points->prev);

in a square leaf cell take out extra points that have come up from below

if(i_tree_current.atLeaf() && (*i_tree_current)->refined){ test line ************************** assert((*i_tree_current)->points->next || (*i_tree_current)->points->prev);

std::printf(" collecting points from removed leaves\n"); assert((*i_tree_current)->points); i_tree_pointlist_current = (*i_tree_current)->points; NtoRemove = (*i_tree_current)->npoints; assert(NtoRemove == 9); center[0] = ((*i_tree_current)->boundary_p1[0] + (*i_tree_current)->boundary_p2[0])/2; center[1] = ((*i_tree_current)->boundary_p1[1] + (*i_tree_current)->boundary_p2[1])/2;

for(i=0,count1=0,count2=0;i<NtoRemove;++i,–i_tree_pointlist_current){ find central point and remove others

 if( (pow(center[0]-(*i_tree_pointlist_current)->x[0],2)
  + pow(center[1]-(*i_tree_pointlist_current)->x[1],2) )
  < pow((*i_tree_pointlist_current)->gridsize/2,2) ){

  ++count1;

keep this central point (*i_tree_pointlist_current)->gridsize *= 3; (*i_tree_pointlist_current)->image->gridsize = (*i_tree_pointlist_current)->gridsize; (*i_tree_current)->points = (*i_tree_pointlist_current);

                 test line  **************************

assert((*i_tree_current)->points->next || (*i_tree_current)->points->prev); assert((*i_tree_pointlist_current)->leaf == *i_tree_current); }else{

++count; // count of total number of points removed ++count2;

reduce the number of particles in all parent cells

First take points out of source plane This is tricky because they are not ordered into square blocks with 9 points in each.

Take point out of the source plane

  assert((*i_tree_pointlist_current)->image);
  point = (*i_tree_pointlist_current)->image;
  assert(point->leaf);
  s_tree_current = point->leaf;

if((*s_tree_current)->npoints < 2) RemoveLeafFromTree(s_tree,&Ntmp); while(!(s_tree_current.atTop())){ –((*s_tree_current)->npoints); if((*s_tree_current)->npoints > 0 && (*s_tree_current)->points == point) (*s_tree_current)->points = point->next;

if((*s_tree_current)->npoints == 0) (*s_tree_current)->points = NULL;

if((*s_tree_current)->npoints == 0 && (*s_tree_current)->prev->npoints == 1){ only remove empty leaves if it will make its parent a leaf assert(s_tree_current.atLeaf()); s_tree->RemoveLeafFromTree(s_tree_current,&Ntmp); s_tree_current.TreeWalkStep(true); // Go to other child. s_tree->RemoveLeafFromTree(s_tree_current,&Ntmp); }else{ s_tree_current.up(); } } assert(boxinbox(*i_tree_current,headbranch));

Do it for top –(s_tree->getTop()->npoints); if(s_tree->getTop()->npoints > 0 && s_tree->getTop()->points == point) s_tree->getTop()->points = point->next;

s_tree_pointlist_current = point; s_tree->pointlist.TakeOutCurrent(s_tree_pointlist_current); point->leaf = NULL; // set leaf to NULL to indicate that point is no longer in tree if(point->head) trashkist->InsertAfterCurrent(point); // collect heads for later trash collection

assert(boxinbox(*i_tree_current,headbranch));

take points out of image plane branch = *i_tree_current; do{ assert((*i_tree_current)->npoints); –((*i_tree_current)->npoints); if((*i_tree_current)->points == (*i_tree_pointlist_current)) (*i_tree_current)->points = NULL;

}while(i_tree_current.up()); i_tree_current = branch; assert(boxinbox(*i_tree_current,headbranch));

if((*i_tree_pointlist_current) == (*i_tree_current)->points) (*i_tree_current)->points = (*i_tree_pointlist_current)->next; point = i_tree->pointlist.TakeOutCurrent(i_tree_pointlist_current); point->leaf = NULL; If point is a head of a memory block add it to trashlist for eventual trash collection if(point->head){ assert(point->head == 8); trashkist->InsertAfterCurrent(point); } } assert(boxinbox(*i_tree_current,headbranch));

} // loop through points in leaf

reassign first point in branches above the current branch = *i_tree_current; do{ assert((*i_tree_current)->npoints); if((*i_tree_current)->points == NULL) (*i_tree_current)->points = branch->points; }while(i_tree_current.up()); i_tree_current = branch;

assert(boxinbox(*i_tree_current,headbranch));

assert(count1 == 1); assert(count2 == 8); assert((*i_tree_current)->npoints == 1); } // if current was leaf that was refined

} // at tree leaf assert((*i_tree_current)->points); assert(boxinbox(*i_tree_current,headbranch));

if( !(i_tree_current.atLeaf()) ) i_tree_current.TreeWalkStep(true); } // while entry current is not a leaf

assert(CurrentIsSquareTree(i_tree)); assert((*i_tree_current)->npoints == 1); assert(i_tree_current.atLeaf()); assert(*i_tree_current == headbranch);

(*i_tree_current)->refined = false;

Free the memory for the points that have been removed. CollectTrash(trashkist,false);

assert(trashkist->Nunits() == 0); if(count) std::printf("FreeBranchesBelow() freed %li points and moved up %li points\n",count,count2); return count; } Removes current from a tree if it is a leaf. Will not remove root of tree.

on output: Current is left at the father of the leaf that was removed. All the points in the leaf that was removed are in its father so the father might be a leaf without Nbucket points. The ->leaf pointer of these points are reassigned to the father.

returns: Pointer to first in list of points that were reassigned. *Npoints = number of points reassigned.

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

SLsimLib/include/Tree.h
SLsimLib/TreeCode_link/KistDriver.cpp
SLsimLib/TreeCode_link/Tree.cpp
SLsimLib/TreeCode_link/tree_maintenance.cpp
SLsimLib/TreeCode_link/TreeDriver.cpp

Classes

Public Member Functions

Public Attributes

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ TreeStruct() [1/2]

◆ TreeStruct() [2/2]

Member Function Documentation

◆ _FindLeaf()

◆ emptyTree()

◆ FindAllBoxNeighborsKist() [1/2]

◆ FindAllBoxNeighborsKist() [2/2]

◆ FindBoxPoint()

◆ NearestNeighborKist()

◆ PointsWithinEllipKist()

◆ PointsWithinKist()

◆ RemoveLeafFromTree()