km_ann.h

高效的k-means算法实现

//
//  KMpoint:
//	A point is represented as a (dimensionless) vector of
//	coordinates, that is, as a pointer to KMcoord.  It is the
//	user's responsibility to be sure that each such vector has
//	been allocated with enough components.  Because only
//	pointers are stored, the values should not be altered
//	through the lifetime of the nearest neighbor data structure.
//  KMpointArray is a dimensionless array of KMpoint.
//  KMdistArray is a dimensionless array of KMdist.
//  KMidxArray is a dimensionless array of KMidx.  This is used for
//	storing buckets of points in the search trees, and for returning
//	the results of k nearest neighbor queries.
//----------------------------------------------------------------------

typedef KMcoord		*KMpoint;		// a point
typedef KMpoint 	*KMpointArray;		// an array of points 
typedef KMdist  	*KMdistArray;		// an array of distances 
typedef KMidx		*KMidxArray;		// an array of point indices

//----------------------------------------------------------------------
//  Point utilities:
//
//	kmDist(dim, p, q)
//	  Returns the squared distances between p and q.
//
//	kmEqualPts(dim, p, q)
//	  Returns true if p and q are the same points.
//
//----------------------------------------------------------------------
//----------------------------------------------------------------------
//  Point and Point-array Allocation/Deallocation:
//
//	Because points (somewhat like strings in C) are stored as
//	pointers.  Consequently, creating and destroying copies of
//	points may require storage allocation.  These procedures do
//	this.
//
//	p = kmAllocPt(dim, c=0)
//	  Allocates storage for a single point, and return a pointer
//	  to it.  The second argument is used to initialize all the
//	  points components.
//
//	kmDeallocPt(p)
//	  Deallocates a point allocated by kmAllocPt().
//
//	pa = kmAllocPts(n, dim)
//	  Allocates an array of n points in dimension d.  It performs
//	  no initialization.
//
// 	kmDeallocPts(pa)
//	  Deallocates points allocated by kmAllocPts().
//----------------------------------------------------------------------
   
KMdist kmDist(				// compute squared distance
    int			dim,			// dimension of space
    KMpoint		p,			// points
    KMpoint		q);

bool kmEqualPts(			// are two points equal?
    int			dim,			// dimension
    KMpoint		p1,			// the points
    KMpoint		p2);

KMpoint kmAllocPt(			// allocate point storage
    int			dim,			// dimension
    KMcoord		c = 0);			// coordinate value (all equal)

void kmDeallocPt(			// deallocate a point
    KMpoint		&p);

KMpointArray kmAllocPts(		// allocate point array
    int			n,			// number of points
    int			dim);			// dimension
   
void kmDeallocPts(			// deallocate a point array
    KMpointArray	&pa);			// the array

//----------------------------------------------------------------------
//  Point and other type copying:
//
//	kmCopyPt(dim, source, dest)
//	  Copies point source to point dest, without allocation.
//
//	dest = kmAllocCopyPt(dim, source)
//	  Allocates storage for and copies a point source to dest.
//
//	kmCopyPts(n, dim, source, dest)
//	  Copies point array source to point dest, without allocation.
//
//	dest = kmAllocCopyPts(n, dim, source)
//	  Allocates storage for and copies a point array source to dest.
//
//	kmCopy(n, source, dest)
//	  A generic copy routine for any time for which "=" is defined.
//
//	kmAllocCopy(n, source, dest)
//	  A generic allocate and copy routine for any time for which
//	  "=" is defined.
//----------------------------------------------------------------------

void kmCopyPt(				// copy point without allocation
    int			dim,			// dimension
    KMpoint		source,			// source point
    KMpoint		dest);			// destination point

KMpoint kmAllocCopyPt(			// allocate and copy point
    int			dim,			// dimension
    KMpoint		source);		// point to copy

void kmCopyPts(				// copy point array without allocation
    int			n,			// number of points
    int			dim,			// dimension
    const KMpointArray	source,			// source point
    KMpointArray	dest);			// destination point

KMpointArray kmAllocCopyPts(		// allocate and copy point array
    int			n,			// number of points
    int			dim,			// dimension
    const KMpointArray	source);		// source point

template <typename Object>
void kmCopy(				// copy anything without allocation
    int			n,			// number of object
    const Object*	source,			// source array
    Object*		dest)			// destination array
{
    for (int i = 0; i < n; i++) {		// copy contents
    	dest[i] = source[i];
    }
}

template <typename Object>
Object* kmAllocCopy(			// allocate and copy anything
    int			n,			// number of object
    const Object*	source)			// source array
{
    Object* dest = new Object[n];		// allocate array
    for (int i = 0; i < n; i++) {		// copy contents
    	dest[i] = source[i];
    }
    return dest;
}

//----------------------------------------------------------------------
//  Global constants and types
//----------------------------------------------------------------------
enum KMtreeType {KM_KD_TREE, KM_BD_TREE};	// tree types
enum		 {KM_LO=0, KM_HI=1};		// splitting indices
enum		 {KM_IN=0, KM_OUT=1};		// shrinking indices

const int KM_STRING_LEN = 100;		// default string length

//----------------------------------------------------------------------
//  Orthogonal (axis aligned) rectangle
//	Orthogonal rectangles are represented by two points, one
//	for the lower left corner (min coordinates) and the other
//	for the upper right corner (max coordinates).
//
//	The constructor initializes from either a pair of coordinates,
//	pair of points, or another rectangle.  Note that all constructors
//	allocate new point storage.  The destructor deallocates this
//	storage.
//
//	BEWARE: Orthogonal rectangles should be passed ONLY BY REFERENCE.
//	(C++'s default copy constructor will not allocate new point
//	storage, then on return the destructor free's storage, and then
//	you get into big trouble in the calling procedure.)
//----------------------------------------------------------------------

class KMorthRect {
public:
    KMpoint	lo;			// rectangle lower bounds
    KMpoint	hi;			// rectangle upper bounds
//
    KMorthRect(			// basic constructor
	int dd,				// dimension of space
	KMcoord l=0,			// default is empty
	KMcoord h=0)
    {  lo = kmAllocPt(dd, l);  hi = kmAllocPt(dd, h);  }

    KMorthRect(			// (almost a) copy constructor
	int dd,				// dimension
	const KMorthRect &r)		// rectangle to copy
    {  lo = kmAllocCopyPt(dd, r.lo);  hi = kmAllocCopyPt(dd, r.hi); }

    KMorthRect(			// construct from points
	int dd,				// dimension
	KMpoint l,			// low point
	KMpoint h)			// hight point
    {  lo = kmAllocCopyPt(dd, l);  hi = kmAllocCopyPt(dd, h);  }

    ~KMorthRect()			// destructor
    {  kmDeallocPt(lo);  kmDeallocPt(hi); }

    bool inside(int dim, KMpoint p);	// is point p inside rectangle?
    					// expand by factor x and store in r
    void expand(int dim, double x, KMorthRect r);
    void sample(int dim, KMpoint p);	// sample point p uniformly
};

void kmAssignRect(		// assign one rect to another
    int			dim,		// dimension (both must be same)
    KMorthRect		&dest,		// destination (modified)
    const KMorthRect	&source);	// source

#endif