AW: libkdtree experiences and questions

[Samuel D. Hayne]

Just hit on reply and didn't post this one in the list so ... :)

Dienstag, 11. November 2008 09:42 Sylvain Bougerel wrote: 
> > 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?

No... just saw that VC got confused by all the _Node definitions.
Changing _Node in this file to anything else solved the problem.
There's no deeper sense in _Ab. :)

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

Hehe yeah. 
It was quick and dirty. 

 
> Same as above, ;-)

Hey ... at least here I tried to set it up as friend class. :) .. didn't
work out though. So... quick and dirty again.

> > #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?

D'oh! My fault. 
Somehow I thought it's included automatically ... but I did it myself.
Yet, many Windows coders should step in that trap.

Don't know how else to avoid that Microsoft macro nonsense.
:-/ Macro's stronger than namespace. Boo!

> 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 :)

You didn't sound patronizing in any way.
I mentioned myself that it won't be the best solution for everyone.

Including an ID in the duplet struct and comparing this one might be a real
solution for everyone... as could  be working with pointers and comparing
those.
In my project I'm sure no two points share the same coordinate. So it's okay
for me.

Just wanted to share the bit of code if someone has the same problem to
solve.

> 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?

In fact I used them:

> > struct not_me   //struct to sort out a coordinate
> > {
> > 	...
> > };
> >
> > struct not_us   //struct to sort out a vector of coordinates
> > {
> >   ...
> > };

...

> > duplet_tree_type::iterator findNearestNeighbor( duplet_tree_type& tree,
duplet* dup_point ) 
> >	{
> >
> >	...
> > 	
> >	duplet_tree_type::const_iterator found = 
> >tree.find_nearest_if(*dup_point, mmax, not_me( dup_point ) ).first;
> >
> >	...
> >
> >	return found;
> >
> >	}


:)


> 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?

I fed erase with one coordinate and hoped that this one coordinate would be
erased.
Just like in your example... where you copy (don't you?) a triplet d0 in the
tree and later delete it with myKDtree.erase(d0).

> 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.

Ahhh. K.
At first I thought I had to rebalance the tree after each erase.
Didn't look too deeply in the KDtree theory. After all... it's pure nonsense
for any tree when I think about it. :D Just by trying I saw that there was
no difference in the output when not doing so... but a pretty speed gain. :D

 
> 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.

Would be really great. :)
What makes things worse is that VC's IntelliSense doesn't get along with
libkdtree...
So I more or less stumbled over erase_exact() by browsing over the code ...
which eventually solved my problem.

Just basically a list of functions and a short explanation would surely make
things easier for people who try to give libkdtree a shot. :)

 
> #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.

Ahh k. That's basically what I do in the application code too.
Doing a first search and feeding the not_us predicate with a vector
containing the searchpoint and it's first neighbor.
So I get searchpoint's third neighbor.

Read a short discussion in this list about using a freaky visitor or doing
it another way at all.
I dropped out there... :D

> 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.

Sure. Just feel free to use me as your personal crash test dummy. 

Sam