ann.h

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

//----------------------------------------------------------------------
// File:			ANN.h
// Programmer:		Sunil Arya and David Mount
// Last modified:	05/03/05 (Release 1.1)
// Description:		Basic include file for approximate nearest
//					neighbor searching.
//----------------------------------------------------------------------
// 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
//		Added copyright and revision information
//		Added ANNcoordPrec for coordinate precision.
//		Added methods theDim, nPoints, maxPoints, thePoints to ANNpointSet.
//		Cleaned up C++ structure for modern compilers
//	Revision 1.1  05/03/05
//		Added fixed-radius k-NN searching
//----------------------------------------------------------------------

//----------------------------------------------------------------------
// ANN - approximate nearest neighbor searching
//	ANN is a library for approximate nearest neighbor searching,
//	based on the use of standard and priority search in kd-trees
//	and balanced box-decomposition (bbd) trees. Here are some
//	references to the main algorithmic techniques used here:
//
//		kd-trees:
//			Friedman, Bentley, and Finkel, ``An algorithm for finding
//				best matches in logarithmic expected time,'' ACM
//				Transactions on Mathematical Software, 3(3):209-226, 1977.
//
//		Priority search in kd-trees:
//			Arya and Mount, ``Algorithms for fast vector quantization,''
//				Proc. of DCC '93: Data Compression Conference, eds. J. A.
//				Storer and M. Cohn, IEEE Press, 1993, 381-390.
//
//		Approximate nearest neighbor search and bbd-trees:
//			Arya, Mount, Netanyahu, Silverman, and Wu, ``An optimal
//				algorithm for approximate nearest neighbor searching,''
//				5th Ann. ACM-SIAM Symposium on Discrete Algorithms,
//				1994, 573-582.
//----------------------------------------------------------------------

#ifndef ANN_H
#define ANN_H

#ifdef WIN32
  //----------------------------------------------------------------------
  // For Microsoft Visual C++, externally accessible symbols must be
  // explicitly indicated with DLL_API, which is somewhat like "extern."
  //
  // The following ifdef block is the standard way of creating macros
  // which make exporting from a DLL simpler. All files within this DLL
  // are compiled with the DLL_EXPORTS preprocessor symbol defined on the
  // command line. In contrast, projects that use (or import) the DLL
  // objects do not define the DLL_EXPORTS symbol. This way any other
  // project whose source files include this file see DLL_API functions as
  // being imported from a DLL, wheras this DLL sees symbols defined with
  // this macro as being exported.
  //----------------------------------------------------------------------
  #ifdef DLL_EXPORTS
	 #define DLL_API __declspec(dllexport)
  #else
	#define DLL_API __declspec(dllimport)
  #endif
  //----------------------------------------------------------------------
  // DLL_API is ignored for all other systems
  //----------------------------------------------------------------------
#else
  #define DLL_API
#endif

//----------------------------------------------------------------------
//  basic includes
//----------------------------------------------------------------------

#include <cmath>			// math includes
#include <iostream>			// I/O streams

//----------------------------------------------------------------------
// Limits
// There are a number of places where we use the maximum double value as
// default initializers (and others may be used, depending on the
// data/distance representation). These can usually be found in limits.h
// (as LONG_MAX, INT_MAX) or in float.h (as DBL_MAX, FLT_MAX).
//
// Not all systems have these files.  If you are using such a system,
// you should set the preprocessor symbol ANN_NO_LIMITS_H when
// compiling, and modify the statements below to generate the
// appropriate value. For practical purposes, this does not need to be
// the maximum double value. It is sufficient that it be at least as
// large than the maximum squared distance between between any two
// points.
//----------------------------------------------------------------------
#ifdef ANN_NO_LIMITS_H					// limits.h unavailable
  #include <cvalues>					// replacement for limits.h
  const double ANN_DBL_MAX = MAXDOUBLE;	// insert maximum double
#else
  #include <climits>
  #include <cfloat>
  const double ANN_DBL_MAX = DBL_MAX;
#endif

#define ANNversion 		"1.1.1"			// ANN version and information
#define ANNversionCmt	""
#define ANNcopyright	"David M. Mount and Sunil Arya"
#define ANNlatestRev	"Aug 4, 2006"

//----------------------------------------------------------------------
//	ANNbool
//	This is a simple boolean type. Although ANSI C++ is supposed
//	to support the type bool, some compilers do not have it.
//----------------------------------------------------------------------

enum ANNbool {ANNfalse = 0, ANNtrue = 1}; // ANN boolean type (non ANSI C++)

//----------------------------------------------------------------------
//	ANNcoord, ANNdist
//		ANNcoord and ANNdist are the types used for representing
//		point coordinates and distances.  They can be modified by the
//		user, with some care.  It is assumed that they are both numeric
//		types, and that ANNdist is generally of an equal or higher type
//		from ANNcoord.	A variable of type ANNdist should be large
//		enough to store the sum of squared components of a variable
//		of type ANNcoord for the number of dimensions needed in the
//		application.  For example, the following combinations are
//		legal:
//
//		ANNcoord		ANNdist
//		---------		-------------------------------
//		short			short, int, long, float, double
//		int				int, long, float, double
//		long			long, float, double
//		float			float, double
//		double			double
//
//		It is the user's responsibility to make sure that overflow does
//		not occur in distance calculation.
//----------------------------------------------------------------------

typedef double	ANNcoord;				// coordinate data type
typedef double	ANNdist;				// distance data type

//----------------------------------------------------------------------
//	ANNidx
//		ANNidx is a point index.  When the data structure is built, the
//		points are given as an array.  Nearest neighbor results are
//		returned as an integer index into this array.  To make it
//		clearer when this is happening, we define the integer type
//		ANNidx.	 Indexing starts from 0.
//		
//		For fixed-radius near neighbor searching, it is possible that
//		there are not k nearest neighbors within the search radius.  To
//		indicate this, the algorithm returns ANN_NULL_IDX as its result.
//		It should be distinguishable from any valid array index.
//----------------------------------------------------------------------

typedef int		ANNidx;					// point index
const ANNidx	ANN_NULL_IDX = -1;		// a NULL point index

//----------------------------------------------------------------------
//	Infinite distance:
//		The code assumes that there is an "infinite distance" which it
//		uses to initialize distances before performing nearest neighbor
//		searches.  It should be as larger or larger than any legitimate
//		nearest neighbor distance.
//
//		On most systems, these should be found in the standard include
//		file <limits.h> or possibly <float.h>.  If you do not have these
//		file, some suggested values are listed below, assuming 64-bit
//		long, 32-bit int and 16-bit short.
//
//		ANNdist ANN_DIST_INF	Values (see <limits.h> or <float.h>)
//		------- ------------	------------------------------------
//		double	DBL_MAX			1.79769313486231570e+308
//		float	FLT_MAX			3.40282346638528860e+38
//		long	LONG_MAX		0x7fffffffffffffff
//		int		INT_MAX			0x7fffffff
//		short	SHRT_MAX		0x7fff
//----------------------------------------------------------------------

const ANNdist	ANN_DIST_INF = ANN_DBL_MAX;

//----------------------------------------------------------------------
//	Significant digits for tree dumps:
//		When floating point coordinates are used, the routine that dumps
//		a tree needs to know roughly how many significant digits there
//		are in a ANNcoord, so it can output points to full precision.
//		This is defined to be ANNcoordPrec.  On most systems these
//		values can be found in the standard include files <limits.h> or
//		<float.h>.  For integer types, the value is essentially ignored.
//
//		ANNcoord ANNcoordPrec	Values (see <limits.h> or <float.h>)
//		-------- ------------	------------------------------------
//		double	 DBL_DIG		15
//		float	 FLT_DIG		6
//		long	 doesn't matter 19
//		int		 doesn't matter 10
//		short	 doesn't matter 5
//----------------------------------------------------------------------

#ifdef DBL_DIG							// number of sig. bits in ANNcoord
	const int	 ANNcoordPrec	= DBL_DIG;
#else
	const int	 ANNcoordPrec	= 15;	// default precision
#endif

//----------------------------------------------------------------------
// Self match?
//	In some applications, the nearest neighbor of a point is not
//	allowed to be the point itself. This occurs, for example, when
//	computing all nearest neighbors in a set.  By setting the
//	parameter ANN_ALLOW_SELF_MATCH to ANNfalse, the nearest neighbor
//	is the closest point whose distance from the query point is
//	strictly positive.
//----------------------------------------------------------------------

const ANNbool	ANN_ALLOW_SELF_MATCH	= ANNtrue;

//----------------------------------------------------------------------
//	Norms and metrics:
//		ANN supports any Minkowski norm for defining distance.  In
//		particular, for any p >= 1, the L_p Minkowski norm defines the
//		length of a d-vector (v0, v1, ..., v(d-1)) to be
//
//				(|v0|^p + |v1|^p + ... + |v(d-1)|^p)^(1/p),
//
//		(where ^ denotes exponentiation, and |.| denotes absolute
//		value).  The distance between two points is defined to be the
//		norm of the vector joining them.  Some common distance metrics
//		include
//
//				Euclidean metric		p = 2
//				Manhattan metric		p = 1
//				Max metric				p = infinity
//
//		In the case of the max metric, the norm is computed by taking
//		the maxima of the absolute values of the components.  ANN is
//		highly "coordinate-based" and does not support general distances
//		functions (e.g. those obeying just the triangle inequality).  It
//		also does not support distance functions based on
//		inner-products.
//
//		For the purpose of computing nearest neighbors, it is not
//		necessary to compute the final power (1/p).  Thus the only
//		component that is used by the program is |v(i)|^p.
//
//		ANN parameterizes the distance computation through the following
//		macros.  (Macros are used rather than procedures for
//		efficiency.) Recall that the distance between two points is
//		given by the length of the vector joining them, and the length
//		or norm of a vector v is given by formula:
//
//				|v| = ROOT(POW(v0) # POW(v1) # ... # POW(v(d-1)))
//
//		where ROOT, POW are unary functions and # is an associative and
//		commutative binary operator mapping the following types:
//
//			**	POW:	ANNcoord				--> ANNdist
//			**	#:		ANNdist x ANNdist		--> ANNdist
//			**	ROOT:	ANNdist (>0)			--> double
//
//		For early termination in distance calculation (partial distance