ann2fig.cpp

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

												// unfilled line object
	ofile << "2 1 0 1 -1 7 0 0 -1 0.000 0 0 -1 0 0 2\n";

	int p0_x = (int) TRANS_X(p0);				// transform endpoints
	int p0_y = (int) TRANS_Y(p0);
	int p1_x = (int) TRANS_X(p1);
	int p1_y = (int) TRANS_Y(p1);
	ofile << "\t"
		 << p0_x << " " << p0_y << " "			// write vertices
		 << p1_x << " " << p1_y << "\n";
}

void writeCaption(								// write caption text
	const ANNorthRect	&bnd_box,				// bounding box
	char				*caption)				// caption
{
	if (!strcmp(caption, "\0")) return;			// null string?
	int px = (int) TRANS_X(bnd_box.lo);			// put .5 in. lower left
	int py = (int) (TRANS_Y(bnd_box.lo) + 0.50 * u_per_in); 
	ofile << "4 0 -1 0 0 0 20 0.0000 4 255 2000 ";
	ofile << px << " " << py << " " << caption << "\\001\n";
}

//----------------------------------------------------------------------
// overlap - test whether a box overlap slicing region
//
//		The slicing region is a 2-dimensional plane in space
//		which contains points (x1, x2, ..., xn) satisfying the
//		n-2 linear equalities:
//
//						xi == slice_val[i]		for i != dim_x, dim_y
//
//		This procedure returns true of the box defined by
//		corner points box.lo and box.hi overlap this plane.
//----------------------------------------------------------------------

ANNbool overlap(const ANNorthRect &box)
{
	for (int i = 0; i < dim; i++) {
		if (i != dim_x && i != dim_y &&
		   (box.lo[i] > slice_val[i] || box.hi[i] < slice_val[i]))
			return ANNfalse;
	}
	return ANNtrue;
}

//----------------------------------------------------------------------
// readTree, recReadTree - inputs tree and outputs figure
//
//		readTree procedure initializes things and then calls recReadTree
//		which does all the work.
//
//		recReadTree reads in a node of the tree, makes any recursive
//		calls as needed to input the children of this node (if internal)
//		and maintains the bounding box.  Note that the bounding box
//		is modified within this procedure, but it is the responsibility
//		of the procedure that it be restored to its original value
//		on return.
//
//		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>
//		Shrinking nodes:
//				shrink <n_bnds>
//						<cut_dim> <cut_val> <side>
//						<cut_dim> <cut_val> <side>
//						... (repeated n_bnds times)
//
//		On reading a leaf we determine whether we should output the
//		cell's points (if dimension = 2 or this cell overlaps the
//		slicing region).  For splitting nodes we check whether the
//		current cell overlaps the slicing plane and whether the
//		cutting dimension coincides with either the x or y drawing
//		dimensions.  If so, we output the corresponding splitting
//		segment.
//----------------------------------------------------------------------

void recReadTree(ANNorthRect &box)
{
	char tag[STRING_LEN];						// tag (leaf, split, shrink)
	int n_pts;									// number of points in leaf
	int idx;									// point index
	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

	ifile >> tag;								// input node tag
	if (strcmp(tag, "leaf") == 0) {				// leaf node

		ifile >> n_pts;							// input number of points
												// check for overlap
		if (dim == 2 || overlap(box)) { 
			for (int i = 0; i < n_pts; i++) {	// yes, write the points
				ifile >> idx;
				writePoint(pts[idx]);
			}
		}
		else {									// input but ignore points
			for (int i = 0; i < n_pts; i++) {
				ifile >> idx;
			}
		}
	}
	else if (strcmp(tag, "split") == 0) {		// splitting node

		ifile >> cd >> cv >> lb >> hb;
		if (lb != box.lo[cd] || hb != box.hi[cd]) {
			Error("Bounding box coordinates are fishy", ANNwarn);
		}

		ANNcoord lv = box.lo[cd];				// save bounds for cutting dim
		ANNcoord hv = box.hi[cd];

		//--------------------------------------------------------------
		//	The following code is rather fragile so modify at your
		//	own risk.  We first decrease the high-end of the bounding
		//	box down to the cutting plane and then read the left subtree.
		//	Then we increase the low-end of the bounding box up to the
		//	cutting plane (thus collapsing the bounding box to a d-1
		//	dimensional hyperrectangle).  Then we draw the projection of
		//	its diagonal if it crosses the slicing plane.  This will have
		//	the effect of drawing its intersection on the slicing plane.
		//	Then we restore the high-end of the bounding box and read
		//	the right subtree.  Finally we restore the low-end of the
		//	bounding box, before returning.
		//--------------------------------------------------------------
		box.hi[cd] = cv;						// decrease high bounds
		recReadTree(box);						// read left subtree
												// check for overlap
		box.lo[cd] = cv;						// increase low bounds
		if (dim == 2 || overlap(box)) {			// check for overlap
			if (cd == dim_x || cd == dim_y) {	// cut through slice plane
				writeLine(box.lo, box.hi);		// draw cutting line
			}
		}
		box.hi[cd] = hv;						// restore high bounds

		recReadTree(box);						// read right subtree
		box.lo[cd] = lv;						// restore low bounds
	}
	else if (strcmp(tag, "shrink") == 0) {		// splitting node

		ANNorthRect inner(dim, box);			// copy bounding box
		ifile >> n_bnds;						// number of bounding sides
		for (int i = 0; i < n_bnds; i++) {
			ifile >> cd >> cv >> sd;			// input bounding halfspace
			ANNorthHalfSpace hs(cd, cv, sd);	// create orthogonal halfspace
			hs.project(inner.lo);				// intersect by projecting
			hs.project(inner.hi);
		}
		if (dim == 2 || overlap(inner)) {
			writeBox(inner);					// draw inner rectangle
		}
		recReadTree(inner);						// read inner subtree
		recReadTree(box);						// read outer subtree
	}
	else {
		Error("Illegal node type in dump file", ANNabort);
	}
}

void readTree(ANNorthRect &bnd_box)
{
	writeHeader();								// output header
	writeBox(bnd_box);							// draw bounding box
	writeCaption(bnd_box, caption);				// write caption
	recReadTree(bnd_box);						// do it
}

//----------------------------------------------------------------------
// readANN - read the ANN dump file
//
//		This procedure reads in the dump file.  See the format below.
//		It first reads the header line with version number.  If the
//		points section is present it reads them (otherwise just leaves
//		points = NULL), and then it reads the tree section.  It inputs
//		the bounding box and determines the parameters for transforming
//		the image to figure units.  It then invokes the procedure
//		readTree to do all the real work.
//
//		Dump File Format: <xxx> = coordinate value (ANNcoord)
//
//		#ANN <version number> <comments> [END_OF_LINE]
//		points <dim> <n_pts>			(point coordinates: this is optional)
//		0 <xxx> <xxx> ... <xxx>			(point indices and coordinates)
//		1 <xxx> <xxx> ... <xxx>
//		  ...
//		tree <dim> <n_pts> <bkt_size>
//		<xxx> <xxx> ... <xxx>			(lower end of bounding box)
//		<xxx> <xxx> ... <xxx>			(upper end of bounding box)
//				If the tree is null, then a single line "null" is
//				output.  Otherwise the nodes of the tree are printed
//				one per line in preorder.  Leaves and splitting nodes 
//				have the following formats:
//		Leaf node:
//				leaf <n_pts> <bkt[0]> <bkt[1]> ... <bkt[n-1]>
//		Splitting nodes:
//				split <cut_dim> <cut_val> <lo_bound> <hi_bound>
//		Shrinking nodes:
//				shrink <n_bnds>
//						<cut_dim> <cut_val> <side>
//						<cut_dim> <cut_val> <side>
//						... (repeated n_bnds times)
//
//		Note: Infinite lo_ and hi_bounds are printed as the special
//				values "-INF" and "+INF", respectively.  We do not
//				check for this, because the current version of ANN
//				starts with a finite bounding box if the tree is
//				nonempty.
//----------------------------------------------------------------------

void readANN()
{
	int j;
	char str[STRING_LEN];						// storage for string
    char version[STRING_LEN];					// storage for version
	int  bkt_size;								// bucket size

	ifile >> str;								// input header
	if (strcmp(str, "#ANN") != 0) {				// incorrect header
		Error("Incorrect header for dump file", ANNabort);
	}
    ifile.getline(version, STRING_LEN);			// get version (ignore)
	ifile >> str;								// get major heading
	if (strcmp(str, "points") == 0) {			// points section
		ifile >> dim;							// read dimension
		ifile >> n_pts;							// number of points
		pts = annAllocPts(n_pts, dim);			// allocate points
		for (int i = 0; i < n_pts; i++) {		// input point coordinates
			int idx;							// point index
			ifile >> idx;						// input point index
			if (idx < 0 || idx >= n_pts) {
				Error("Point index is out of range", ANNabort);
			}
			for (j = 0; j < dim; j++) {
				ifile >> pts[idx][j];			// read point coordinates
			}
		}
		ifile >> str;							// get next major heading
	}
	if (strcmp(str, "tree") == 0) {				// tree section
		ifile >> dim;							// read dimension
		if (dim_x > dim || dim_y > dim) {
			Error("Dimensions out of bounds", ANNabort);
		}
		ifile >> n_pts;							// number of points
		ifile >> bkt_size;						// bucket size (ignored)
												// read bounding box
		ANNorthRect bnd_box(dim);				// create bounding box
		for (j = 0; j < dim; j++) {
			ifile >> bnd_box.lo[j];				// read box low coordinates
		}
		for (j = 0; j < dim; j++) {
			ifile >> bnd_box.hi[j];				// read box high coordinates
		}
												// compute scaling factors
		double box_len_x = bnd_box.hi[dim_x] - bnd_box.lo[dim_x];
		double box_len_y = bnd_box.hi[dim_y] - bnd_box.lo[dim_y];
												// longer side determines scale
		if (box_len_x > box_len_y) scale = u_size/box_len_x;
		else					   scale = u_size/box_len_y;
												// compute offsets
		offset_x = u_low_x - scale*bnd_box.lo[dim_x];
		offset_y = u_low_y + scale*bnd_box.hi[dim_y];
		readTree(bnd_box);						// read the tree and process
	}
	else if (strcmp(str, "null") == 0) return;	// empty tree
	else {
		cerr << "Input string: " << str << "\n";
		Error("Illegal ann format.  Expecting section heading", ANNabort);
	}
}

//----------------------------------------------------------------------
// Main program
//
// Gets the command-line arguments and invokes the main scanning
// procedure.
//----------------------------------------------------------------------

main(int argc, char **argv)
{
	getArgs(argc, argv);						// get input arguments
	readANN();									// read the dump file
}