libkdtree experiences and questions

[Paul Harris]

Excellent stuff, I've put it into a test_hayne.cpp file, and attached it to
a bug report.

Sylvain and I are debugging stuff stuff now, we'll add it to the test suite
:)

thanks again,
Paul


2008/11/11 Sam Hayne <Sam.Hayne at gmx.de>

>
> Paul Harris wrote:
>
> > Hi Sam,
>
> > great email, lots of detail
>
> Thx. If it helps you in any way I'm glad.
> (Hope those issues weren't all caused by VS or my edits. :D )
>
> > 3.1)
> > > I always ended up with runtime errors using erase().  :(
>
> > Could you please boil it down to a simple test case?  (eg look at
> test_kdtree.cpp, just make up a new .cpp file that builds a tree and then >
> somehow crashes or asserts).
>
>
> Puhh... wasn't that easy to create an simple example (as in my case I got
> the points out of a bitmap).
> But here a bit lengthy one - it crashes deterministically each time.
>
> In my case erase() failed to delete point (41, 189)... deleting some other
> point instead.
> Eventually resulting in this runtime error:
> http://img359.imageshack.us/img359/4623/runtimeerrordz4.jpg
>
>
> //=======
> //Defs:
> //========
>
> 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];
>         //typedef boost::shared_ptr<duplet> ptr;
> };
>
> typedef KDTree::KDTree<2, duplet,
> std::pointer_to_binary_function<duplet,int,double> > duplet_tree_type;
>
> inline double return_dup( duplet d, int k ) { return d[k]; }
>
>
>
>
> //=======
> //main:
> //========
>
>        duplet_tree_type dupl_tree_test(std::ptr_fun(return_dup));
>         std::vector<duplet> vDuplets;
>
>        //srand(time(0));
>        int randy1 = 0;
>        int randy2 = 0;
>        for (int i=0; i<700; i++)
>        {
>                //create coordinate for new duplet
>                randy1+=2;
>                randy1=randy1%255;
>                randy2+=3;
>                randy2=randy2%255;
>                //randy1 = rand() % 255;
>                //randy2 = rand() % 255;
>
>                //new duplet
>                duplet super_dupre = { {randy1, randy2} };
>
>                //check if duplet with same coordinate already in
> vector/tree. If not: insert in vector and tree
>                 duplet_tree_type::iterator pItr =
>
> dupl_tree_test.find_nearest(super_dupre,std::numeric_limits<double>::max()).
> first;
>                if (*pItr!=super_dupre)
>                {
>                        dupl_tree_test.insert(super_dupre);
>                        vDuplets.push_back(super_dupre);
>                }
>
>        }
>
>        dupl_tree_test.optimise();
>
>        int elements;
>
>        while (vDuplets.size()>0) //delete all duplets from tree which are
> in the vector
>        {
>                elements = vDuplets.size();
>
>
>                duplet element_to_erase = vDuplets.back();
>                vDuplets.pop_back();
>
>                dupl_tree_test.erase(element_to_erase); //erase() : will
> probably erase wrong element sooner or later
>                //dupl_tree_test.erase_exact(element_to_erase);
> //erase_exact(): works
>
>
>                //debug stuff:
>                 duplet_tree_type::iterator pItr =
>
> dupl_tree_test.find_nearest(element_to_erase,std::numeric_limits<double>::ma
> x()).first;
>                duplet nearest_to_element = *pItr;
>                if (nearest_to_element==element_to_erase)
>                {
>                        // element still in tree... wrong element must have
> been erased
>                        int u = 7; //set breakpoint here
>                }
>        }
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20081111/ce5e96b6/attachment.htm