ann.h

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

	int annkFRSearch(					// approx fixed-radius kNN search
		ANNpoint		q,				// query point
		ANNdist			sqRad,			// squared radius
		int				k = 0,			// number of near neighbors to return
		ANNidxArray		nn_idx = NULL,	// nearest neighbor array (modified)
		ANNdistArray	dd = NULL,		// dist to near neighbors (modified)
		double			eps=0.0);		// error bound

	int theDim()						// return dimension of space
		{ return dim; }

	int nPoints()						// return number of points
		{ return n_pts; }

	ANNpointArray thePoints()			// return pointer to points
		{  return pts;  }
};

//----------------------------------------------------------------------
// kd- and bd-tree splitting and shrinking rules
//		kd-trees supports a collection of different splitting rules.
//		In addition to the standard kd-tree splitting rule proposed
//		by Friedman, Bentley, and Finkel, we have introduced a
//		number of other splitting rules, which seem to perform
//		as well or better (for the distributions we have tested).
//
//		The splitting methods given below allow the user to tailor
//		the data structure to the particular data set.  They are
//		are described in greater details in the kd_split.cc source
//		file.  The method ANN_KD_SUGGEST is the method chosen (rather
//		subjectively) by the implementors as the one giving the
//		fastest performance, and is the default splitting method.
//
//		As with splitting rules, there are a number of different
//		shrinking rules.  The shrinking rule ANN_BD_NONE does no
//		shrinking (and hence produces a kd-tree tree).  The rule
//		ANN_BD_SUGGEST uses the implementors favorite rule.
//----------------------------------------------------------------------

enum ANNsplitRule {
		ANN_KD_STD				= 0,	// the optimized kd-splitting rule
		ANN_KD_MIDPT			= 1,	// midpoint split
		ANN_KD_FAIR				= 2,	// fair split
		ANN_KD_SL_MIDPT			= 3,	// sliding midpoint splitting method
		ANN_KD_SL_FAIR			= 4,	// sliding fair split method
		ANN_KD_SUGGEST			= 5};	// the authors' suggestion for best
const int ANN_N_SPLIT_RULES		= 6;	// number of split rules

enum ANNshrinkRule {
		ANN_BD_NONE				= 0,	// no shrinking at all (just kd-tree)
		ANN_BD_SIMPLE			= 1,	// simple splitting
		ANN_BD_CENTROID			= 2,	// centroid splitting
		ANN_BD_SUGGEST			= 3};	// the authors' suggested choice
const int ANN_N_SHRINK_RULES	= 4;	// number of shrink rules

//----------------------------------------------------------------------
//	kd-tree:
//		The main search data structure supported by ANN is a kd-tree.
//		The main constructor is given a set of points and a choice of
//		splitting method to use in building the tree.
//
//		Construction:
//		-------------
//		The constructor is given the point array, number of points,
//		dimension, bucket size (default = 1), and the splitting rule
//		(default = ANN_KD_SUGGEST).  The point array is not copied, and
//		is assumed to be kept constant throughout the lifetime of the
//		search structure.  There is also a "load" constructor that
//		builds a tree from a file description that was created by the
//		Dump operation.
//
//		Search:
//		-------
//		There are two search methods:
//
//			Standard search (annkSearch()):
//				Searches nodes in tree-traversal order, always visiting
//				the closer child first.
//			Priority search (annkPriSearch()):
//				Searches nodes in order of increasing distance of the
//				associated cell from the query point.  For many
//				distributions the standard search seems to work just
//				fine, but priority search is safer for worst-case
//				performance.
//
//		Printing:
//		---------
//		There are two methods provided for printing the tree.  Print()
//		is used to produce a "human-readable" display of the tree, with
//		indenation, which is handy for debugging.  Dump() produces a
//		format that is suitable reading by another program.  There is a
//		"load" constructor, which constructs a tree which is assumed to
//		have been saved by the Dump() procedure.
//		
//		Performance and Structure Statistics:
//		-------------------------------------
//		The procedure getStats() collects statistics information on the
//		tree (its size, height, etc.)  See ANNperf.h for information on
//		the stats structure it returns.
//
//		Internal information:
//		---------------------
//		The data structure consists of three major chunks of storage.
//		The first (implicit) storage are the points themselves (pts),
//		which have been provided by the users as an argument to the
//		constructor, or are allocated dynamically if the tree is built
//		using the load constructor).  These should not be changed during
//		the lifetime of the search structure.  It is the user's
//		responsibility to delete these after the tree is destroyed.
//
//		The second is the tree itself (which is dynamically allocated in
//		the constructor) and is given as a pointer to its root node
//		(root).  These nodes are automatically deallocated when the tree
//		is deleted.  See the file src/kd_tree.h for further information
//		on the structure of the tree nodes.
//
//		Each leaf of the tree does not contain a pointer directly to a
//		point, but rather contains a pointer to a "bucket", which is an
//		array consisting of point indices.  The third major chunk of
//		storage is an array (pidx), which is a large array in which all
//		these bucket subarrays reside.  (The reason for storing them
//		separately is the buckets are typically small, but of varying
//		sizes.  This was done to avoid fragmentation.)  This array is
//		also deallocated when the tree is deleted.
//
//		In addition to this, the tree consists of a number of other
//		pieces of information which are used in searching and for
//		subsequent tree operations.  These consist of the following:
//
//		dim						Dimension of space
//		n_pts					Number of points currently in the tree
//		n_max					Maximum number of points that are allowed
//								in the tree
//		bkt_size				Maximum bucket size (no. of points per leaf)
//		bnd_box_lo				Bounding box low point
//		bnd_box_hi				Bounding box high point
//		splitRule				Splitting method used
//
//----------------------------------------------------------------------

//----------------------------------------------------------------------
// Some types and objects used by kd-tree functions
// See src/kd_tree.h and src/kd_tree.cpp for definitions
//----------------------------------------------------------------------
class ANNkdStats;				// stats on kd-tree
class ANNkd_node;				// generic node in a kd-tree
typedef ANNkd_node*	ANNkd_ptr;	// pointer to a kd-tree node

class DLL_API ANNkd_tree: public ANNpointSet {
protected:
	int				dim;				// dimension of space
	int				n_pts;				// number of points in tree
	int				bkt_size;			// bucket size
	ANNpointArray	pts;				// the points
	ANNidxArray		pidx;				// point indices (to pts array)
	ANNkd_ptr		root;				// root of kd-tree
	ANNpoint		bnd_box_lo;			// bounding box low point
	ANNpoint		bnd_box_hi;			// bounding box high point

	void SkeletonTree(					// construct skeleton tree
		int				n,				// number of points
		int				dd,				// dimension
		int				bs,				// bucket size
		ANNpointArray pa = NULL,		// point array (optional)
		ANNidxArray pi = NULL);			// point indices (optional)

public:
	ANNkd_tree(							// build skeleton tree
		int				n = 0,			// number of points
		int				dd = 0,			// dimension
		int				bs = 1);		// bucket size

	ANNkd_tree(							// build from point array
		ANNpointArray	pa,				// point array
		int				n,				// number of points
		int				dd,				// dimension
		int				bs = 1,			// bucket size
		ANNsplitRule	split = ANN_KD_SUGGEST);	// splitting method

	ANNkd_tree(							// build from dump file
		std::istream&	in);			// input stream for dump file

	~ANNkd_tree();						// tree destructor

	void annkSearch(					// approx k near neighbor search
		ANNpoint		q,				// query point
		int				k,				// number of near neighbors to return
		ANNidxArray		nn_idx,			// nearest neighbor array (modified)
		ANNdistArray	dd,				// dist to near neighbors (modified)
		double			eps=0.0);		// error bound

	void annkPriSearch( 				// priority k near neighbor search
		ANNpoint		q,				// query point
		int				k,				// number of near neighbors to return
		ANNidxArray		nn_idx,			// nearest neighbor array (modified)
		ANNdistArray	dd,				// dist to near neighbors (modified)
		double			eps=0.0);		// error bound

	int annkFRSearch(					// approx fixed-radius kNN search
		ANNpoint		q,				// the query point
		ANNdist			sqRad,			// squared radius of query ball
		int				k,				// number of neighbors to return
		ANNidxArray		nn_idx = NULL,	// nearest neighbor array (modified)
		ANNdistArray	dd = NULL,		// dist to near neighbors (modified)
		double			eps=0.0);		// error bound

	int theDim()						// return dimension of space
		{ return dim; }

	int nPoints()						// return number of points
		{ return n_pts; }

	ANNpointArray thePoints()			// return pointer to points
		{  return pts;  }

	virtual void Print(					// print the tree (for debugging)
		ANNbool			with_pts,		// print points as well?
		std::ostream&	out);			// output stream

	virtual void Dump(					// dump entire tree
		ANNbool			with_pts,		// print points as well?
		std::ostream&	out);			// output stream
								
	virtual void getStats(				// compute tree statistics
		ANNkdStats&		st);			// the statistics (modified)
};								

//----------------------------------------------------------------------
//	Box decomposition tree (bd-tree)
//		The bd-tree is inherited from a kd-tree.  The main difference
//		in the bd-tree and the kd-tree is a new type of internal node
//		called a shrinking node (in the kd-tree there is only one type
//		of internal node, a splitting node).  The shrinking node
//		makes it possible to generate balanced trees in which the
//		cells have bounded aspect ratio, by allowing the decomposition
//		to zoom in on regions of dense point concentration.  Although
//		this is a nice idea in theory, few point distributions are so
//		densely clustered that this is really needed.
//----------------------------------------------------------------------

class DLL_API ANNbd_tree: public ANNkd_tree {
public:
	ANNbd_tree(							// build skeleton tree
		int				n,				// number of points
		int				dd,				// dimension
		int				bs = 1)			// bucket size
		: ANNkd_tree(n, dd, bs) {}		// build base kd-tree

	ANNbd_tree(							// build from point array
		ANNpointArray	pa,				// point array
		int				n,				// number of points
		int				dd,				// dimension
		int				bs = 1,			// bucket size
		ANNsplitRule	split  = ANN_KD_SUGGEST,	// splitting rule
		ANNshrinkRule	shrink = ANN_BD_SUGGEST);	// shrinking rule

	ANNbd_tree(							// build from dump file
		std::istream&	in);			// input stream for dump file
};

//----------------------------------------------------------------------
//	Other functions
//	annMaxPtsVisit		Sets a limit on the maximum number of points
//						to visit in the search.
//  annClose			Can be called when all use of ANN is finished.
//						It clears up a minor memory leak.
//----------------------------------------------------------------------

DLL_API void annMaxPtsVisit(	// max. pts to visit in search
	int				maxPts);	// the limit

DLL_API void annClose();		// called to end use of ANN

#endif