kd_dump.cpp

c++实现的KNN库:建立高维度的K-d tree,实现K邻域搜索

	ANNidxArray the_pidx;						// point index storage
	ANNkd_ptr the_root;							// root of the tree

	the_root = annReadDump(						// read the dump file
		in,										// input stream
		BD_TREE,								// expecting a bd-tree
		the_pts,								// point array (returned)
		the_pidx,								// point indices (returned)
		the_dim, the_n_pts, the_bkt_size,		// basic tree info (returned)
		the_bnd_box_lo, the_bnd_box_hi);		// bounding box info (returned)

												// create a skeletal tree
	SkeletonTree(the_n_pts, the_dim, the_bkt_size, the_pts, the_pidx);
	bnd_box_lo = the_bnd_box_lo;
	bnd_box_hi = the_bnd_box_hi;

	root = the_root;							// set the root
}

//----------------------------------------------------------------------
//	annReadDump - read a dump file
//
//		This procedure reads a dump file, constructs a kd-tree
//		and returns all the essential information needed to actually
//		construct the tree.	 Because this procedure is used for
//		constructing both kd-trees and bd-trees, the second argument
//		is used to indicate which type of tree we are expecting.
//----------------------------------------------------------------------

static ANNkd_ptr annReadDump(
	istream				&in,					// input stream
	ANNtreeType			tree_type,				// type of tree expected
	ANNpointArray		&the_pts,				// new points (returned)
	ANNidxArray			&the_pidx,				// point indices (returned)
	int					&the_dim,				// dimension (returned)
	int					&the_n_pts,				// number of points (returned)
	int					&the_bkt_size,			// bucket size (returned)
	ANNpoint			&the_bnd_box_lo,		// low bounding point (ret'd)
	ANNpoint			&the_bnd_box_hi)		// high bounding point (ret'd)
{
	int j;
	char str[STRING_LEN];						// storage for string
	char version[STRING_LEN];					// ANN version number
	ANNkd_ptr the_root = NULL;

	//------------------------------------------------------------------
	//	Input file header
	//------------------------------------------------------------------
	in >> str;									// input header
	if (strcmp(str, "#ANN") != 0) {				// incorrect header
		annError("Incorrect header for dump file", ANNabort);
	}
	in.getline(version, STRING_LEN);			// get version (ignore)

	//------------------------------------------------------------------
	//	Input the points
	//			An array the_pts is allocated and points are read from
	//			the dump file.
	//------------------------------------------------------------------
	in >> str;									// get major heading
	if (strcmp(str, "points") == 0) {			// points section
		in >> the_dim;							// input dimension
		in >> the_n_pts;						// number of points
												// allocate point storage
		the_pts = annAllocPts(the_n_pts, the_dim);
		for (int i = 0; i < the_n_pts; i++) {	// input point coordinates
			ANNidx idx;							// point index
			in >> idx;							// input point index
			if (idx < 0 || idx >= the_n_pts) {
				annError("Point index is out of range", ANNabort);
			}
			for (j = 0; j < the_dim; j++) {
				in >> the_pts[idx][j];			// read point coordinates
			}
		}
		in >> str;								// get next major heading
	}
	else {										// no points were input
		annError("Points must be supplied in the dump file", ANNabort);
	}

	//------------------------------------------------------------------
	//	Input the tree
	//			After the basic header information, we invoke annReadTree
	//			to do all the heavy work.  We create our own array of
	//			point indices (so we can pass them to annReadTree())
	//			but we do not deallocate them.	They will be deallocated
	//			when the tree is destroyed.
	//------------------------------------------------------------------
	if (strcmp(str, "tree") == 0) {				// tree section
		in >> the_dim;							// read dimension
		in >> the_n_pts;						// number of points
		in >> the_bkt_size;						// bucket size
		the_bnd_box_lo = annAllocPt(the_dim);	// allocate bounding box pts
		the_bnd_box_hi = annAllocPt(the_dim);

		for (j = 0; j < the_dim; j++) {			// read bounding box low
			in >> the_bnd_box_lo[j];
		}
		for (j = 0; j < the_dim; j++) {			// read bounding box low
			in >> the_bnd_box_hi[j];
		}
		the_pidx = new ANNidx[the_n_pts];		// allocate point index array
		int next_idx = 0;						// number of indices filled
												// read the tree and indices
		the_root = annReadTree(in, tree_type, the_pidx, next_idx);
		if (next_idx != the_n_pts) {			// didn't see all the points?
			annError("Didn't see as many points as expected", ANNwarn);
		}
	}
	else {
		annError("Illegal dump format.	Expecting section heading", ANNabort);
	}
	return the_root;
}

//----------------------------------------------------------------------
// annReadTree - input tree and return pointer
//
//		annReadTree reads in a node of the tree, makes any recursive
//		calls as needed to input the children of this node (if internal).
//		It returns a pointer to the node that was created.	An array
//		of point indices is given along with a pointer to the next
//		available location in the array.  As leaves are read, their
//		point indices are stored here, and the point buckets point
//		to the first entry in the array.
//
//		Recall that these are the formats.	The tree is given in
//		preorder.
//
//		Leaf node:
//				leaf <n_pts> <bkt[0]> <bkt[1]> ... <bkt[n-1]>
//		Splitting nodes:
//				split <cut_dim> <cut_val> <lo_bound> <hi_bound>
//
//		For bd-trees:
//
//		Shrinking nodes:
//				shrink <n_bnds>
//						<cut_dim> <cut_val> <side>
//						<cut_dim> <cut_val> <side>
//						... (repeated n_bnds times)
//----------------------------------------------------------------------

static ANNkd_ptr annReadTree(
	istream				&in,					// input stream
	ANNtreeType			tree_type,				// type of tree expected
	ANNidxArray			the_pidx,				// point indices (modified)
	int					&next_idx)				// next index (modified)
{
	char tag[STRING_LEN];						// tag (leaf, split, shrink)
	int n_pts;									// number of points in leaf
	int cd;										// cut dimension
	ANNcoord cv;								// cut value
	ANNcoord lb;								// low bound
	ANNcoord hb;								// high bound
	int n_bnds;									// number of bounding sides
	int sd;										// which side

	in >> tag;									// input node tag

	if (strcmp(tag, "null") == 0) {				// null tree
		return NULL;
	}
	//------------------------------------------------------------------
	//	Read a leaf
	//------------------------------------------------------------------
	if (strcmp(tag, "leaf") == 0) {				// leaf node

		in >> n_pts;							// input number of points
		int old_idx = next_idx;					// save next_idx
		if (n_pts == 0) {						// trivial leaf
			return KD_TRIVIAL;
		}
		else {
			for (int i = 0; i < n_pts; i++) {	// input point indices
				in >> the_pidx[next_idx++];		// store in array of indices
			}
		}
		return new ANNkd_leaf(n_pts, &the_pidx[old_idx]);
	}
	//------------------------------------------------------------------
	//	Read a splitting node
	//------------------------------------------------------------------
	else if (strcmp(tag, "split") == 0) {		// splitting node

		in >> cd >> cv >> lb >> hb;

												// read low and high subtrees
		ANNkd_ptr lc = annReadTree(in, tree_type, the_pidx, next_idx);
		ANNkd_ptr hc = annReadTree(in, tree_type, the_pidx, next_idx);
												// create new node and return
		return new ANNkd_split(cd, cv, lb, hb, lc, hc);
	}
	//------------------------------------------------------------------
	//	Read a shrinking node (bd-tree only)
	//------------------------------------------------------------------
	else if (strcmp(tag, "shrink") == 0) {		// shrinking node
		if (tree_type != BD_TREE) {
			annError("Shrinking node not allowed in kd-tree", ANNabort);
		}

		in >> n_bnds;							// number of bounding sides
												// allocate bounds array
		ANNorthHSArray bds = new ANNorthHalfSpace[n_bnds];
		for (int i = 0; i < n_bnds; i++) {
			in >> cd >> cv >> sd;				// input bounding halfspace
												// copy to array
			bds[i] = ANNorthHalfSpace(cd, cv, sd);
		}
												// read inner and outer subtrees
		ANNkd_ptr ic = annReadTree(in, tree_type, the_pidx, next_idx);
		ANNkd_ptr oc = annReadTree(in, tree_type, the_pidx, next_idx);
												// create new node and return
		return new ANNbd_shrink(n_bnds, bds, ic, oc);
	}
	else {
		annError("Illegal node type in dump file", ANNabort);
		exit(0);								// to keep the compiler happy
	}
}