libkdtree experiences and questions

Mon Nov 10 18:19:28 UTC 2008

Hello! :)

First: Thx for libkdtree!
(and sorry for posting in the wrong maillist at first... :-/ )

Started to use libkdtree last week and it speeds up things a LOT compared to
a naive simple search in my case.

Version used:
Copied the current files out of here manually:
http://git.debian.org/?p=libkdtree/libkdtree.git;a=tree

Here the experiences I made. :)

As the posting is a bit longer, a short summary:

1) compiler errors in VC2005 + solution 

I don't claim that they are the best way of solving the errors - but maybe
you want to make some changes in your project to ease lives of VC users. :)

2) "My" 2D Nearest Neighbor search solution (basically some changes to the
previously mentioned approach)

...as the previously mentioned ones didn't compile for me at all and
ultimately resulted in a heap corruption (shared_ptr behaved like a beast
here).

3) some questions

=====================================
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; 

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

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

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

kdtree.hpp:

comment away "__throw_exception_again;" in line 1175 => unknown identifier

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;

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

==================
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()??

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?

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

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

Sam Hayne