NearestNeighbours.h

Go to the documentation of this file.

#ifndef _H_NEARESTNEIGHBOURS
#define _H_NEARESTNEIGHBOURS

#include<vector>

using namespace std;

template < typename cur_type >
class NearestNeighbours {
        public:

        unsigned int   max;     
        unsigned int   size;    
        double         maxdist; 
        vector<int>    *ids;    
        vector<double> *dists;  
        NearestNeighbours( unsigned int k ) {
                this->max     = k;
                this->size    = 0;
                this->maxdist = 0;
                this->ids     = new vector< int >();
                this->dists   = new vector< double >();
        }

        void insert( double dist, cur_type *element ) {
                if ( this->max > this->size ) {
                        /* Less than k neighbours have been found, so add this one */
                        if ( dist > this->maxdist ) {
                                this->maxdist = dist;
                        }
                        this->ids->push_back( element->getID() );
                        this->dists->push_back( dist );
                        this->size++;
                } else if ( dist >= this->maxdist ) {
                        /* The element is further away than the k current neighbours, so do not add this one */
                        return;
                } else {
                        /* The element is closer than one of the current neighbours, so replace that one */
                        double newmaxdist = 0;
                        for (unsigned int i = 0; i < this->ids->size(); i++) {
                                        if ( this->dists->at( i ) == this->maxdist ) {
                                                this->dists->at( i ) = dist;
                                                this->ids->at( i )   = element->getID();
                                                for (; i < this->ids->size(); i++) {
                                                        if (this->dists->at( i ) > newmaxdist) {
                                                                newmaxdist = this->dists->at( i );
                                                        }
                                                }
                                        break;
                                }
                                if (this->dists->at( i ) > newmaxdist) {
                                        newmaxdist = this->dists->at( i );
                                }
                        }
                        this->maxdist = newmaxdist;
                }
        }

        void insert( double dist, int index ) {
                if ( this->max > this->size ) {
                        /* Less than k neighbours have been found, so add this one */
                        if ( dist > this->maxdist ) {
                                this->maxdist = dist;
                        }
                        this->ids->push_back( index );
                        this->dists->push_back( dist );
                        this->size++;
                } else if ( dist >= this->maxdist ) {
                        /* The element is further away than the k current neighbours, so do not add this one */
                        return;
                } else {
                        /* The element is closer than one of the current neighbours, so replace that one */
                        double newmaxdist = 0;
                        for (unsigned int i = 0; i < this->ids->size(); i++) {
                                        if (this->dists->at( i ) == this->maxdist) {
                                                this->dists->at( i ) = dist;
                                                this->ids->at( i )   = index;
                                                        for (; i < this->ids->size(); i++) {
                                                        if (this->dists->at( i ) > newmaxdist) {
                                                                newmaxdist = this->dists->at( i );
                                                        }
                                        }
                                        break;
                                }
                                if (this->dists->at( i ) > newmaxdist) {
                                        newmaxdist = this->dists->at( i );
                                }
                        }
                        this->maxdist = newmaxdist;
                }
        }


        static double minimumDistance(vector <double> p, const cur_type * const in) {
                const unsigned int dim = in->getDimension();
                double ret = 0;
                for ( unsigned int i = 0; i < dim; i++ )  {
                        if (p[ i ] < in->getMinCoordinateOnDimension( i )) {
                                ret += (in->getMinCoordinateOnDimension( i ) - p[ i ]) * (in->getMinCoordinateOnDimension( i ) - p[ i ]);
                        } else if (p[ i ] > in->getMaxCoordinateOnDimension( i )) {
                                ret += (p[ i ] - in->getMaxCoordinateOnDimension( i )) * (p[ i ] - in->getMaxCoordinateOnDimension( i ));
                        } else {
                                ret += 0;
                        }
                }
                return ret;
        }

};



#endif

---