Can I build a KDTree of pointers to objects?

Paul Harris paulharris at computer.org
Mon Apr 28 02:28:53 UTC 2008


a functor is many things.  one way to think about it, its just a function
with state.   but when it comes to defining for sort and for accessors, its
really just a way to exactly specify the "function signature"...

define your accessor

   struct access_location_ptr
   {
      typedef double result_type;

      double operator()( const Point & e, int k ) const { return
e.location[k]; }
      double operator()( const Point * e, int k ) const { return
e->location[k]; }
   };





define your tree.

   typedef KDTree::KDTree<3,Point const*,access_location_ptr> PtrTree;


get your data

vector<Point> data;   lots of .push_backs() to fill the vector

NOTE: you could just use a malloc() or a plain array eg Point points[100];
and use those addresses.  just as long as the memory locations don't change
once the tree is loaded.   Vectors are handy because they manage all the
memory alloc/deallocs/resizes for you.


fill the tree
PtrTree tree;
for ( vect::iterator p = data.begin() etc ; ++p )
  tree.insert( &*p );  // dereference iterator, then take the address

optimise
tree.optimise();

now, don't allow the vector to move, copy, don't add anything else to the
vector or remove anything.  the kdtree now points to the items in the
vector, if the memory block that the vector manages is moved due to a memory
resize, or the items are reordered, then the tree will either be filled with
invalidated pointers, or all the items will be mixed up.

note that the accessor has 2 ways of calling it - one with a pointer, one
without.
useful for

Point whatnot; // set it up with the location
result = tree.find_nearest(whatnot, etc);

so it can access both whatnot (directly through reference) or via pointers
(in the tree).

see ya
Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080428/50bed447/attachment.htm 


More information about the libkdtree-devel mailing list