libkdtree experiences and questions

[Sylvain Bougerel]

On Tue, Nov 11, 2008 at 2:19 AM, Sam Hayne <Sam.Hayne at gmx.de> wrote:
> Hello! :)
>
>
> As the posting is a bit longer, a short summary:
>
>
> =====================================
> 1) compiler errors in VC2005 + solution
> =====================================
>
> allocator.hpp:
>
> typedef confusion
>
> error: kdtree++/kdtree.hpp(95) : error C2059: syntax error : '<'
>
> solved by:
> rename all _Node to e.g. _Node_Ab in this file starting from line 21:
>
> old: typedef typename _Node<_Tp> _Node;
> new: typedef typename _Node<_Tp> _Node_Ab;
>

Okay, that's not nice, although I think that VC++ does not respect the
standard here, we should still make the library portable.

Just one question? why did you put _Ab as a suffix? A particular reason?

>
> node.hpp:
>
> confusion:
> reserved #defines (in windef.h) "near" and "far" used as variable names:
> => rename near and far to something like near_N and far_N, starting from
> line 337
>

Ah yeah, I remember dealing with something like that once. Hum, well,
it should be changed too, I guess.

>
>
> iterator.hpp:
>
> error: error C2248: 'KDTree::_Iterator<_Val,_Ref,_Ptr>::operator *' : cannot
> access private member declared in class 'KDTree::_Iterator<_Val,_Ref,_Ptr>'
>
> solved by:
>
> add "public:" in line 110:
>
>  template <typename _Val, typename _Ref, typename _Ptr>
>    class _Iterator : protected _Base_iterator
>    {
>     public:    //added
>       typedef _Val value_type;
>       ...
>
>

Ok I dunno weather it was g++ error of VC2005 error. But this rings a big:
"DON'T DO THIS" bell in my mind.

>
>
> error C2247: 'KDTree::_Base_iterator::_M_node' not accessible because
> 'KDTree::_Iterator<_Val,_Ref,_Ptr>' uses 'protected' to inherit from
> 'KDTree::_Base_iterator'
>
> solved by:
>
> line 108: change "protected" to public
> old: class _Iterator : protected _Base_iterator
> new: class _Iterator : public _Base_iterator
>
> (may be really bad though..)
>

Same as above, ;-)

>
>
> kdtree.hpp:
>
> comment away "__throw_exception_again;" in line 1175 => unknown identifier
>

Ohla, okay this is not nice: I think we should not use it cause it's
pure libstdc++ stuff. It should be equivalent in most case to a
simple:
     throw;
I'm gonna check why they use this in the library and not the above.

>
>
> error in test_kdtree.cpp:
>
> warning C4003: not enough actual parameters for macro 'max'
> error C2589: '(' : illegal token on right side of '::'
> error C2059: syntax error : '::'
>
> caused by: *t.find_nearest(s,std::numeric_limits<double>::max()).first;
>
> Solved by: Undefine min/max previously defined in windows.h:
>
> #undef max;
> #undef min;
> triplet result =
> *t.find_nearest(s,std::numeric_limits<double>::max()).first;
>
>

Urg, this is really ugly... can you tell us why you actually had
"windows.h" included here? Did you added it for some reason, or does
it get included by another file?

test_kdtree.cpp should be plain standard... like it should not require
platform specific headers...

>
>
> change in triplet definition:
>
> struct triplet {
>        typedef int value_type;
>
>        inline value_type operator[](size_t const N) const { return d[N]; }
>        inline bool operator==(triplet const& other) {
>                return this->d[0] == other.d[0] && this->d[1] == other.d[1]
> && this->d[2] == other.d[2];
>        }
>
>
>        value_type d[3];
> };
>
>
>
>
>
>
>
> ===========================
> 2) Nearest neighbor search
> ===========================
>
> One thing: As I was really unable to do a pointer comparison of the "duplet"
> struct I chose to compare coordinates.

Yeah, you won't actually get to do this in the nearest neighbor
search, because, well, it compares by coordinates... I know it my
sound patronizing here, but I don't know how to put it otherwise :)

> The tradeoff (of course): If two points have the same coordinate a 3rd one
> will be found as nearest neighbor.
>
> So I wouldn't claim this being the smartest code out there... but it works
> in my case and maybe it will help someone out there:
>
> //struct for a 2D point
> struct duplet {
>        typedef int value_type;
>
>        inline value_type operator[](size_t const N) const { return d[N]; }
>        inline bool operator==(duplet const& other) const
>        {
>                return this->d[0] == other.d[0] && this->d[1] == other.d[1];
>
>        }
>
>        inline bool operator!=(duplet const& other) const
>        {
>                return this->d[0] != other.d[0] || this->d[1] != other.d[1];
>
>        }
>
>        value_type d[2];
> };
>
> inline double return_dup( duplet d, int k ) { return d[k]; }
>
> typedef KDTree::KDTree<2, duplet,
> std::pointer_to_binary_function<duplet,int,double> > duplet_tree_type;
>
>
> struct not_me   //struct to sort out a coordinate
> {
>        duplet* me;
>        not_me(duplet* m) : me(m) {}
>
>        bool operator()( KDTree::_Node< duplet > const* n ) const
>        {
>                return n->_M_value != *me;
>        }
>
>        bool operator()( const duplet & n ) const
>        {
>                return n != *me;
>        }
> };
>
> struct not_us   //struct to sort out a vector of coordinates
> {
>        std::vector<duplet> us;
>        not_us(std::vector<duplet> m) : us(m) {}
>
>        bool operator()( KDTree::_Node< duplet > const* n ) const
>        {
>                //return n->_M_value != *me;
>                bool bNotContained = TRUE;
>                for (int i=0; i<us.size(); i++)
>                        if (n->_M_value == us[i]) bNotContained = FALSE;
>                return bNotContained;
>        }
>
>        bool operator()( const duplet & n ) const
>        {
>                /* return n != *me; */
>                bool bNotContained = TRUE;
>                for (int i=0; i<us.size(); i++)
>                        if (n == us[i]) bNotContained = FALSE;
>                return bNotContained;
>        }
>
> };
>
> //just to feed function with iterators... though making no usage of their
> advantages duplet_tree_type::iterator findNearestNeighbor( duplet_tree_type&
> tree, duplet_tree_type::iterator it ) {
>        /////!!!! Will not find NN if search point and NN have same
> coordinates as coordinates are compared!!!
>        duplet tmpTT = *it;
>        return findNearestNeighbor(tree, &tmpTT); }
>
>
> duplet_tree_type::iterator findNearestNeighbor( duplet_tree_type& tree,
> duplet* dup_point ) {
>        /////!!!! Will not find NN if search point and NN have same
> coordinates as coordinates are compared!!!
>
> #undef max;             //undef windows.h max and min
> #undef min;
>
>        float mmax = std::numeric_limits<float>::max();
>        duplet_tree_type::const_iterator found = tree.find_nearest_if(
> *dup_point, mmax, not_me( dup_point ) ).first;
>
>        return found;
>
> }
>
> // to sort out a vector of points...
> duplet_tree_type::iterator findNearestNeighbor_except( duplet_tree_type&
> tree, duplet* dup_point, const std::vector<duplet>& exceptionlist  ) {
>        /////!!!! Will not find NN if search point and NN have same
> coordinates as coordinates are compared!!!
>
> #undef max;             //undef windows.h max and min
> #undef min;
>
>        float mmax = std::numeric_limits<float>::max();
>        duplet_tree_type::const_iterator found = tree.find_nearest_if(
> *dup_point, mmax, not_us( exceptionlist ) ).first;
>
>        return found;
> }
>
>
>
>
>
> usage:
>
> duplet_tree_type dupl_tree_test(std::ptr_fun(return_dup));
>
> duplet d0 = { {1,4} }; dupl_tree_test.insert(d0); duplet d1 = { {4,2} };
> dupl_tree_test.insert(d1); duplet d2 = { {3,2} }; dupl_tree_test.insert(d2);
> duplet d3 = { {5,6} }; dupl_tree_test.insert(d3); duplet d4 = { {2,2} };
> dupl_tree_test.insert(d4);
>
> dupl_tree_test.optimise();
>
> duplet searchPoint = {{3,2}};
>
> //duplet_tree_type::iterator pItr =
> dupl_tree_test.find_nearest(searchPoint,std::numeric_limits<double>::max()).
> first;
> //duplet d_result = *findNearestNeighbor(dupl_tree_test, pItr);
>
> duplet d_result = *findNearestNeighbor(dupl_tree_test, &searchPoint); //will
> return point (2,2)
>
> std::vector<duplet> exceptionlist;
> exceptionlist.push_back(d0);
> exceptionlist.push_back(d4);
>
> d_result = *findNearestNeighbor_except(dupl_tree_test, &searchPoint,
> exceptionlist); //will return point (3,2)
>
>

Wao. It looks really complicated. Did this library really forced you
to do that? Shame on me...

Hum, did you try using "find_nearest_if()". There is a predicate that
you can place at the end of the function in order to distinguish which
is the point you want to get. The trick is that it makes the search
function goes through all the points located at the same coordinate.
Could this help you better?

>
> ==================
> 3) Some questions
> ==================
>
> 3.1)
>
> I always ended up with runtime errors using erase().  :(
>
> I even did a optimise() after every erase() but sooner or later erase()
> obviously tried to delete a value which had already been deleted.
>
> Debugging showed that instead of a point (187,74) the point (176,74) was
> deleted.
> Soon later when trying to delete (176,74) the program crashed with a runtime
> error.
>
> erase_exact() solved this though. Is this intended to happen with erase()??
>

erase will work only on points that are taken from the tree itself,
like references or through an iterator. Did you try to specify a
coordinate and hoped that all the point at the coordinate would be
erased?

>
> 3.2) When should optimise() be called? Just at the beginning? After one
> third of a ... let's say 700 Nodes containing tree have been erased?

Ahah good question. It depends on the kind of data you are working on.
If you are using truly random data, you might not even need to call
it, because if the data is truly random your tree won't really be
unbalanced, and you'll have little gain (or even no gain at all)

If you are using real time data, which are usually clustered in some
positions, it is more difficult to say. Only through profiling can you
find out about this.

>
> 3.3) Could you pleaaaaaaaaase :) provide libkdtree starters with some sort
> of minimanual?
> It's really time consuming (and frustrating) to
> * find out what all those parameters do
> * how a struct for "find_nearest_if()" works

Oh, well, seemed like you've tried it but did not manage to make it
work. Humm, I thinks some nice ppl like Paul are working on
documenting.

Well it should work with the same type of predicates that are necessary for:
std::foreach_if()
std::find_if()
etc.
it's something along the lines:

struct my_predicate
{
   bool operator (const value_type& my_const_ref)
   {
      // some operation that returns true or false
   }
};

> * and what definition necessities there are, so a user defined object can be
> put in a libkdtree.
>
> ..just by looking deeper in the code and fishing out some infos from the
> mailing list.
>
> 3.4) Someone mentioned doing a "Find_N_NearestNeighbors" search could be
> done by feeding find_nearest_if() with a fitting struct.
> How would this look like? I can't see how/where to store the points...
>

You can, but the operation can be troublesome currently. And it wont
be very optimized.
It seems lots of people actually need this feature, but I'm working on
something else at the moment, so you'll have to stick with the current
interface.

So this is how you could do it, but other member of the mailing list
can have other solution. You can make repeated call to find_nearest_if
with a predicate that return false if for the value that have been
found by the previous call. So your predicate needs to remember the
values found in the previous call.

#include<algorithm>
typedef your_kdtree_definition_here tree_type;

struct not_in_pred
{
   bool operator (const tree_type::value_type& my_const_ref)
   {
      return !std::find(ptrs.begin(), ptrs.end(), &my_const_ref);
   }

   std::vector<tree_type::value_type*> ptrs; // vector are faster for small sets
};

not_in_pred not_in;
// add first nearest to the predicate
not_in.ptrs.push_back(&(*(my_tree.find_nearest())));
// add second nearest to the predicate
not_in.ptrs.push_back(&(*(my_tree.find_nearest_if(not_in))));
// add third nearest to the predicate
not_in.ptrs.push_back(&(*(my_tree.find_nearest_if(not_in))));
// etc... stop when you want.

Okay, this is written from the top of my head, you doubt it compiles.
I just hope it will put you on the right track.

>
> Best wishes and I hope this lib finds its way into boost one day, :)
>

Haha, I don't think we're up to boost standard yet. So I'm not so
stressed about inclusion into boost, although that would be quite an
achievement...

I'll take a deeper look at your comments concerning compatibilities
with VC2005. I might need you to try some patch to check that they
both compile on VC2005 and g++-4.3. I'll let you know.

Thanks for the feedback,

Sylvain