worklist.cc

#include "worklist.hh"
#include <cmath>

//Given the min, max of the grid, this class constructs an abstrct grid with boxes of side 1
//The box walker resides in is assume to be in the center
//One can adjust the favored walking direction by altering grid_center, i.e. where you would like your cluster to center.
//This center can be on the grid, or it can be off
//Assess the worklist generated by this class in std::vector<unsigned long int> worklist, using the decoder provided.

wl_gen::wl_gen(int *min, int *max, int* grid_center):
			g(SGrid(min, max)), ncell(1), max_thr(1)
			{
					int bmin[2], bmax[2];
					//Calculate the min coord of the walker, which should lie in the center of the grid
					bmin[0]=int(0.5*(max[0]-1-min[0]));
					bmin[1]=int(0.5*(max[1]-1-min[1]));
					bmax[0]=bmin[0]+1;
					bmax[1]=bmin[1]+1;
					walker = Box<int>(bmin,bmax);
					box_dist<int>(walker, false);
					est_threshold(bmin, bmax,1);
		std::sort(g.boxes.begin(), g.boxes.end(), weighted_sort(grid_center, &g, &walker));
					encoder(false, false, 0);
			}

//Use this if you wish to gives a predefine vector of threshold distances
wl_gen::wl_gen(int *min, int*max, std::vector<int> thr):
			g(SGrid(min, max)), ncell(1), max_thr(1), user_def_thr(thr)
			{
					int bmin[2], bmax[2];
					//Calculate the min coord of the walker, which should lie in the center of the grid
					bmin[0]=int(0.5*(max[0]-1-min[0]));
					bmin[1]=int(0.5*(max[1]-1-min[1]));
					bmax[0]=bmin[0]+1;
					bmax[1]=bmin[1]+1;
					walker = Box<int>(bmin,bmax);
					box_dist<int>(walker, false);
					est_threshold();
		std::sort(g.boxes.begin(),g.boxes.end(),seq_sort(&g));
					encoder(true, false, 0);

			}

//Use this if you wish to divide the walker cell into a subgrid
//ncell is the number of cells in one row. ncell*ncell is the total number of cells
wl_gen::wl_gen(int *min, int*max, int max_thr_, int ncell_):
			g(SGrid(min, max)), ncell(ncell_) ,max_thr(max_thr_*max_thr_*ncell*ncell)
			{
		//creating the walker box
		int wmin[2], wmax[2];
		wmin[0]=int(0.5*(max[0]-1-min[0]));
		wmin[1]=int(0.5*(max[1]-1-min[1]));
		wmax[0]=wmin[0]+1;
		wmax[1]=wmin[1]+1;
		walker = Box<int>(wmin, wmax);

		//creating subgrid within walker box
					double bmin[2], bmax[2];
		double dcell = 1/ double (ncell);
					bmin[0]=0.5* double (max[0]-1-min[0]);
					bmin[1]=0.5* double (max[1]-1-min[1]);
		for (int j=0; j<ncell; j++){
			bmin[1]= double (wmin[1])+j*dcell;
			bmax[1] = bmin[1] + dcell;
			for(int i=0; i<ncell; i++){
				bmin[0] = double (wmin[0])+i*dcell;
				bmax[0] = bmin[0]+dcell;
				//printf("box (%g %g) (%g %g)\n",bmin[0], bmin[1], bmax[0], bmax[1]);
				walker_cells.push_back(Box<double>(bmin, bmax));
			}
		}
		std::vector<Box<double> >::iterator it;
		int nwl=1;
		for(it=walker_cells.begin();it!=walker_cells.end();++it){
			reset();
			box_dist<double>((*it), true);
			std::sort(g.boxes.begin(), g.boxes.end(), dist_sort(&g));
			encoder(false, true, nwl);
			nwl++;
		}
			}

void wl_gen::reset(){
	std::vector<Box<int> >::iterator it;
	for (it=g.boxes.begin(); it!=g.boxes.end();++it){
		(*it).min_d = 0;
		(*it).type = 0;
	}
}

//a convenient function to calculate square distances
template <typename T>
T wl_gen::dsq(T x1, T y1, T x2, T y2){
	return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}

//establish the shortest distance from any box on the grid to the walker box
//the box being passed in can be the walker box, or the cells within walker box
template <typename T>
void wl_gen::box_dist(Box<T> b, bool subgrid){
	T x1 = b.min[0];
	T y1 = b.min[1];
	T x2 = b.max[0];
	T y2 = b.max[1];
	std::vector<Box<int> >::iterator it;
	for (it=g.boxes.begin(); it!=g.boxes.end();++it){
		std::vector<T> lens;
		if(int((*it).min[0]) == walker.min[0] and int((*it).min[1]) == walker.min[1]) lens.push_back( T(0) );

		else{
			//if the box belongs to the same row/column as the walker, compute distance from point to edge
			if( y1 > (*it).min[1] and y2 < (*it).max[1]) {
				lens.push_back(dsq<T>(x1, 0, T((*it).min[0]),0));
				lens.push_back(dsq<T>(x2, 0, T((*it).min[0]),0));
				lens.push_back(dsq<T>(x1, 0, T((*it).max[0]),0));
				lens.push_back(dsq<T>(x2, 0, T((*it).max[0]),0));
			}
			else if( x1 > (*it).min[0] and x2 < (*it).max[0]){
				lens.push_back(dsq<T>(y1, 0, T((*it).min[1]),0));
									lens.push_back(dsq<T>(y2, 0, T((*it).min[1]),0));
									lens.push_back(dsq<T>(y1, 0, T((*it).max[1]),0));
									lens.push_back(dsq<T>(y2, 0, T((*it).max[1]),0));
			}

			//compute distances from each vertex of the walker cell to each vertex of a box
			lens.push_back(dsq<T>(x1,y1,T((*it).min[0]),T((*it).min[1])));
			lens.push_back(dsq<T>(x1,y1,T((*it).max[0]),T((*it).max[1])));
			lens.push_back(dsq<T>(x1,y1,T((*it).min[0]),T((*it).max[1])));
			lens.push_back(dsq<T>(x1,y1,T((*it).max[0]),T((*it).min[1])));
			lens.push_back(dsq<T>(x2,y2,T((*it).min[0]),T((*it).min[1])));
			lens.push_back(dsq<T>(x2,y2,T((*it).max[0]),T((*it).max[1])));
			lens.push_back(dsq<T>(x2,y2,T((*it).min[0]),T((*it).max[1])));
			lens.push_back(dsq<T>(x2,y2,T((*it).max[0]),T((*it).min[1])));
			lens.push_back(dsq<T>(x1,y2,T((*it).min[0]),T((*it).min[1])));
			lens.push_back(dsq<T>(x1,y2,T((*it).max[0]),T((*it).max[1])));
			lens.push_back(dsq<T>(x1,y2,T((*it).min[0]),T((*it).max[1])));
			lens.push_back(dsq<T>(x1,y2,T((*it).max[0]),T((*it).min[1])));
			lens.push_back(dsq<T>(x2,y1,T((*it).min[0]),T((*it).min[1])));
			lens.push_back(dsq<T>(x2,y1,T((*it).max[0]),T((*it).max[1])));
			lens.push_back(dsq<T>(x2,y1,T((*it).min[0]),T((*it).max[1])));
			lens.push_back(dsq<T>(x2,y1,T((*it).max[0]),T((*it).min[1])));
		}
		//sort to find shortest distance
		std::sort(lens.begin(), lens.end());

		//if subgrid is enabled, use the subgrid length as unit 1.
		if (subgrid) {
			int min_d_ = round(*(lens.begin())*ncell*ncell);
			//printf("min_d =%d\n", min_d_);
			//std::cout << "min_d = " << *(lens.begin()) << "\n";
			if(min_d_<=max_thr) {
				(*it).min_d = min_d_;
				(*it).type = 1;
			}
		}
		else (*it).min_d = *(lens.begin());
	}
}


//if using user define threshold distance,
//this function mark the boxes within each threshold
void wl_gen::est_threshold(){
	std::vector<int>::iterator it;
	std::vector<Box<int> >::iterator bo;
	int index =1;
	for(it=user_def_thr.begin();it!=user_def_thr.end();++it){
		for(bo=g.boxes.begin();bo!=g.boxes.end();++bo){
			if((*bo).min_d<(*it) and (*bo).type==0) {
				(*bo).type = index;
			}
		}
		index++;
	}
}
//if not using predefined threshold, this is the function to define it, recursively
void wl_gen::est_threshold(int *min, int *max, int index){
	//Parameters passed in is the bounding box, starting with walker box itself
	//index must be 1 plz
	int x1 = walker.min[0];
	int y1 = walker.min[1];
	int x2 = walker.max[0];
	int y2 = walker.max[1];
	//Find the longest distance from the box where the walker is to the bounding box
	std::vector<int> lens;
	lens.push_back(dsq<int>(x1,y1,min[0], min[1]));
	lens.push_back(dsq<int>(x1,y1,max[0], max[1]));
	lens.push_back(dsq<int>(x1,y1,min[0], max[1]));
	lens.push_back(dsq<int>(x1,y1,max[0], min[1]));
	lens.push_back(dsq<int>(x2,y2,min[0], min[1]));
	lens.push_back(dsq<int>(x2,y2,max[0], max[1]));
	lens.push_back(dsq<int>(x2,y2,min[0], max[1]));
	lens.push_back(dsq<int>(x2,y2,max[0], min[1]));
	lens.push_back(dsq<int>(x1,y2,min[0], min[1]));
	lens.push_back(dsq<int>(x1,y2,max[0], max[1]));
	lens.push_back(dsq<int>(x1,y2,min[0], max[1]));
	lens.push_back(dsq<int>(x1,y2,max[0], min[1]));
	lens.push_back(dsq<int>(x2,y1,min[0], min[1]));
	lens.push_back(dsq<int>(x2,y1,max[0], max[1]));
	lens.push_back(dsq<int>(x2,y1,min[0], max[1]));
	lens.push_back(dsq<int>(x2,y1,max[0], min[1]));
	std::sort(lens.begin(), lens.end());
	int largest = *(lens.end()-1);
	//Mark each box type 1 if the box-walker shortest distance is smaller than the threshold distance
	std::vector<Box<int> >::iterator it;
	int new_min[2], new_max[2];
	new_min[0]=min[0];new_min[1]=min[1];new_max[0]=max[0];new_max[1]=max[1];
	bool update=false;
	for(it=g.boxes.begin(); it!=g.boxes.end(); ++it){
		if((*it).min_d<=largest and (*it).type==0) {
			update=true;
			(*it).type=index;
			if((*it).min[0]<new_min[0]) new_min[0]=(*it).min[0];
			if((*it).min[1]<new_min[1]) new_min[1]=(*it).min[1];
			if((*it).max[0]>new_max[0]) new_max[0]=(*it).max[0];
			if((*it).max[1]>new_max[1]) new_max[1]=(*it).max[1];
		}
	}
	// How to effectively stop?
	if(!update) return;
	else{
		threshold.push_back(largest);
	}
	if(update) {
		est_threshold(new_min, new_max, index+1);
	}
   }


//encode the box relative coordinate to walker box, and its current threshold in one integer
//if subgrid is enabled, the first encoded integer would give 0, 0, [worklist_number].
// Remember [worklist_number] starts at 1.
void wl_gen::encoder(bool usr_def_thr, bool subgrid, int nwl){
	//encode the box id relative to the walker
	//(-1,1) means take a step to the left and up
	//each encoded integer also give the threshold distance
	//Use only after sorting boxes
	if(subgrid) {
		unsigned long int encode = nwl;
		worklist.push_back(encode);
	}
	std::vector<Box<int> >::iterator it;

	for(it=g.boxes.begin(); it!=g.boxes.end(); ++it){
		if(!((*it).type==0)){
			int x = (*it).min[0] - walker.min[0];
			int y = (*it).min[1] - walker.min[1];
		//	printf("x = %d, y =%d ", x, y);
			unsigned int thr_dist;
			if(subgrid) thr_dist = (*it).min_d;
			else{
				if(!usr_def_thr) thr_dist = (unsigned int) *(threshold.begin()+(*it).type-1);
				else thr_dist = (unsigned int) *(user_def_thr.begin()+(*it).type-1);
			}
		//	printf("thr = %u \n ", thr_dist);
			int sx =0, sy=0;
			if(x<0) { sx=1; x*=(-1);}
			if(y<0) { sy=1; y*=(-1);}
			if((x>127 or y>127) or thr_dist >65535) {
				printf("Box coordinates or threshold too large.\nBox coords are allowed 7 bits; threshold 2 bytes.\n");
				printf("x= %d, y= %d, threshold =%d\n", x, y, thr_dist);
				exit(EXIT_FAILURE);
			}
			else {
				unsigned long int encode = (x<<24)+(sx<<31)+(y<<16)+(sy<<23)+thr_dist;
				worklist.push_back(encode);
			}
		}

	}
}