kd_dump.cpp

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

//----------------------------------------------------------------------
// File:			kd_dump.cc
// Programmer:		David Mount
// Description:		Dump and Load for kd- and bd-trees
// Last modified:	01/04/05 (Version 1.0)
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount.  All Rights Reserved.
// 
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN).  This software is provided under
// the provisions of the Lesser GNU Public License (LGPL).  See the
// file ../ReadMe.txt for further information.
// 
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose.  It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
// History:
//	Revision 0.1  03/04/98
//		Initial release
//	Revision 1.0  04/01/05
//		Moved dump out of kd_tree.cc into this file.
//		Added kd-tree load constructor.
//----------------------------------------------------------------------
// This file contains routines for dumping kd-trees and bd-trees and
// reloading them. (It is an abuse of policy to include both kd- and
// bd-tree routines in the same file, sorry.  There should be no problem
// in deleting the bd- versions of the routines if they are not
// desired.)
//----------------------------------------------------------------------

#include "kd_tree.h"					// kd-tree declarations
#include "bd_tree.h"					// bd-tree declarations

using namespace std;					// make std:: available

//----------------------------------------------------------------------
//		Constants
//----------------------------------------------------------------------

const int		STRING_LEN		= 500;	// maximum string length
const double	EPSILON			= 1E-5; // small number for float comparison

enum ANNtreeType {KD_TREE, BD_TREE};	// tree types (used in loading)

//----------------------------------------------------------------------
//		Procedure declarations
//----------------------------------------------------------------------

static ANNkd_ptr annReadDump(			// read dump file
	istream				&in,					// input stream
	ANNtreeType			tree_type,				// type of tree expected
	ANNpointArray		&the_pts,				// new points (if applic)
	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
	ANNpoint			&the_bnd_box_hi);		// high bounding point

static ANNkd_ptr annReadTree(			// read tree-part of dump file
	istream				&in,					// input stream
	ANNtreeType			tree_type,				// type of tree expected
	ANNidxArray			the_pidx,				// point indices (modified)
	int					&next_idx);				// next index (modified)

//----------------------------------------------------------------------
//	ANN kd- and bd-tree Dump Format
//		The dump file begins with a header containing the version of
//		ANN, an optional section containing the points, followed by
//		a description of the tree.	The tree is printed in preorder.
//
//		Format:
//		#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>
//
//		For bd-trees:
//
//		Shrinking nodes:
//				shrink <n_bnds>
//						<cut_dim> <cut_val> <side>
//						<cut_dim> <cut_val> <side>
//						... (repeated n_bnds times)
//----------------------------------------------------------------------

void ANNkd_tree::Dump(					// dump entire tree
		ANNbool with_pts,				// print points as well?
		ostream &out)					// output stream
{
	out << "#ANN " << ANNversion << "\n";
	out.precision(ANNcoordPrec);		// use full precision in dumping
	if (with_pts) {						// print point coordinates
		out << "points " << dim << " " << n_pts << "\n";
		for (int i = 0; i < n_pts; i++) {
			out << i << " ";
			annPrintPt(pts[i], dim, out);
			out << "\n";
		}
	}
	out << "tree "						// print tree elements
		<< dim << " "
		<< n_pts << " "
		<< bkt_size << "\n";

	annPrintPt(bnd_box_lo, dim, out);	// print lower bound
	out << "\n";
	annPrintPt(bnd_box_hi, dim, out);	// print upper bound
	out << "\n";

	if (root == NULL)					// empty tree?
		out << "null\n";
	else {
		root->dump(out);				// invoke printing at root
	}
	out.precision(0);					// restore default precision
}

void ANNkd_split::dump(					// dump a splitting node
		ostream &out)					// output stream
{
	out << "split " << cut_dim << " " << cut_val << " ";
	out << cd_bnds[ANN_LO] << " " << cd_bnds[ANN_HI] << "\n";

	child[ANN_LO]->dump(out);			// print low child
	child[ANN_HI]->dump(out);			// print high child
}

void ANNkd_leaf::dump(					// dump a leaf node
		ostream &out)					// output stream
{
	if (this == KD_TRIVIAL) {			// canonical trivial leaf node
		out << "leaf 0\n";				// leaf no points
	}
	else{
		out << "leaf " << n_pts;
		for (int j = 0; j < n_pts; j++) {
			out << " " << bkt[j];
		}
		out << "\n";
	}
}

void ANNbd_shrink::dump(				// dump a shrinking node
		ostream &out)					// output stream
{
	out << "shrink " << n_bnds << "\n";
	for (int j = 0; j < n_bnds; j++) {
		out << bnds[j].cd << " " << bnds[j].cv << " " << bnds[j].sd << "\n";
	}
	child[ANN_IN]->dump(out);			// print in-child
	child[ANN_OUT]->dump(out);			// print out-child
}

//----------------------------------------------------------------------
// Load kd-tree from dump file
//		This rebuilds a kd-tree which was dumped to a file.	 The dump
//		file contains all the basic tree information according to a
//		preorder traversal.	 We assume that the dump file also contains
//		point data.	 (This is to guarantee the consistency of the tree.)
//		If not, then an error is generated.
//
//		Indirectly, this procedure allocates space for points, point
//		indices, all nodes in the tree, and the bounding box for the
//		tree.  When the tree is destroyed, all but the points are
//		deallocated.
//
//		This routine calls annReadDump to do all the work.
//----------------------------------------------------------------------

ANNkd_tree::ANNkd_tree(					// build from dump file
	istream				&in)					// input stream for dump file
{
	int the_dim;								// local dimension
	int the_n_pts;								// local number of points
	int the_bkt_size;							// local number of points
	ANNpoint the_bnd_box_lo;					// low bounding point
	ANNpoint the_bnd_box_hi;					// high bounding point
	ANNpointArray the_pts;						// point storage
	ANNidxArray the_pidx;						// point index storage
	ANNkd_ptr the_root;							// root of the tree

	the_root = annReadDump(						// read the dump file
		in,										// input stream
		KD_TREE,								// expecting a kd-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
}

ANNbd_tree::ANNbd_tree(					// build bd-tree from dump file
	istream				&in) : ANNkd_tree()		// input stream for dump file
{
	int the_dim;								// local dimension
	int the_n_pts;								// local number of points
	int the_bkt_size;							// local number of points
	ANNpoint the_bnd_box_lo;					// low bounding point
	ANNpoint the_bnd_box_hi;					// high bounding point
	ANNpointArray the_pts;						// point storage