Wednesday, January 6, 2010

Nearest Neighbour on KD-Tree in C++ and Boost

Wikipedia describes the pseudo-code for computing the nearest neighbour (nn) on an already built KDtree. Here you have a boost implementation of Nearest Neighbour with Kd-tree in boost.

5 comments:

  1. The link to the zip file is broken !

    ReplyDelete
  2. Getting these many errors when I compiled in Eclipse.
    Build of configuration Debug for project K-NN ****

    In file included from ../kdtree.cpp:1:
    ../kdtree.h:5:42: warning: boost/numeric/ublas/matrix.hpp: No such file or directory
    .
    ../kdtree.h:15: error: 'boost' has not been declared
    ../kdtree.h:15: error: expected initializer before '<' token
    ../kdtree.h:17: error: expected constructor, destructor, or type conversion before '&' token
    ../kdtree.h:20: error: 'boost' has not been declared
    ../kdtree.h:20: error: expected initializer before '<' token
    ../kdtree.h:23: error: 'boost' has not been declared
    ../kdtree.h:23: error: expected initializer before '<' token
    ../kdtree.h:24: error: 'boost' has not been declared
    ../kdtree.h:24: error: expected initializer before '<' token
    ../kdtree.h:29: error: expected constructor, destructor, or type conversion before '&' token
    ../kdtree.h: In constructor 'KDTREE::Node::Node(KDTREE::coordinate, unsigned int)':
    ../kdtree.h:37: warning: 'KDTREE::Node::_idx' will be initialized after
    ../kdtree.h:34: warning: 'KDTREE::Node* KDTREE::Node::_right'
    ../kdtree.h:40: warning: when initialized here
    ../kdtree.h: At global scope:
    ../kdtree.h:46: error: 'boost' has not been declared
    ../kdtree.h:46: error: expected initializer before '<' token
    ../kdtree.h:72: error: ISO C++ forbids declaration of 'Points' with no type
    ../kdtree.h:72: error: 'Points' declared as an 'inline' field
    ../kdtree.h:72: error: expected ';' before '&' token
    ../kdtree.h:86: error: 'NNreturn' does not name a type
    ../kdtree.h:90: error: 'Points' does not name a type
    ../kdtree.h:123: error: 'NNreturn' does not name a type
    ../kdtree.h:128: error: ISO C++ forbids declaration of 'Point' with no type
    ../kdtree.h:128: error: expected ',' or '...' before '&' token
    ../kdtree.h: In constructor 'KDTREE::KDtree::KDtree(unsigned int, unsigned int)':
    ../kdtree.h:59: error: '_ps' was not declared in this scope
    ../kdtree.h:62: error: 'rand' was not declared in this scope
    ../kdtree.h:62: error: 'RAND_MAX' was not declared in this scope
    ../kdtree.cpp: At global scope:
    ../kdtree.cpp:6: error: ISO C++ forbids declaration of 'Points' with no type
    ../kdtree.cpp:6: error: expected ',' or '...' before '&' token
    ../kdtree.cpp: In function 'std::ostream& KDTREE::operator<<(std::ostream&, int)':
    ../kdtree.cpp:8: error: 'ps' was not declared in this scope
    ../kdtree.cpp: In member function 'KDTREE::Node* KDTREE::KDtree::_build(KDTREE::Ind, unsigned int)':
    ../kdtree.cpp:65: error: '_ps' was not declared in this scope
    ../kdtree.cpp: In member function 'void KDTREE::KDtree::depthFirstVisit(KDTREE::Node*) const':
    ../kdtree.cpp:109: error: '_ps' was not declared in this scope
    ../kdtree.cpp: At global scope:
    ../kdtree.cpp:120: error: 'NNreturn' does not name a type
    ../kdtree.cpp:182: error: ISO C++ forbids declaration of 'Point' with no type
    ../kdtree.cpp:182: error: expected ',' or '...' before '&' token
    ../kdtree.cpp: In member function 'double KDTREE::KDtree::_distance(unsigned int, int) const':
    ../kdtree.cpp:185: error: 'p' was not declared in this scope
    ../kdtree.cpp:188: error: '_ps' was not declared in this scope
    ../kdtree.cpp: In member function 'unsigned int KDTREE::KDtree::_partition(KDTREE::Ind&, unsigned int, unsigned int, unsigned int)':
    ../kdtree.cpp:232: error: '_ps' was not declared in this scope
    ../kdtree.cpp: In member function 'void KDTREE::KDtree::__dump_data_with_ind(KDTREE::Ind&, unsigned int)':
    ../kdtree.cpp:269: error: '_ps' was not declared in this scope
    make: *** [kdtree.o] Error 1

    ReplyDelete
  3. kdtree.h:123:12: error: extra qualification ‘KDTREE::KDtree::’ on member ‘_returnNearest’


    Pls fix this.. complied in g++

    ReplyDelete
  4. Remove KDtree:: from KDtree::_returnNearest and no error.

    ReplyDelete