Alternatives to libkdtree?

[Paul Harris]

if all you need to do is find a nearest point, you could try binning
your points and then searching within a range of cells...

eg: create a hash_map<> that uses a 'location' as a key.  use
boost::hash to help create the hashing function.

calculate the location-key by dividing the item's location by a range
factor and then rounding to an integer.
the range factor something you would tune depending on how far you
want to search for the nearest item.  if you want to search 10 units
away, then factor might be 10.

then fill the hash.   the key is rounded, the data is list or vector
of pointers that point to the items in that cell.

for (items::iterator item)
  lookuphash[ calc_key(*item) ].push_back( &*item );

then to look up at location xy you would do...

Key key = calc_key(xyz);
for (int i = -1; i != 2; ++i)
  for (int j = -1; j != 2; ++j)
  {
    Key key2 ( key.x + i, key.y + j );
    process_items(  lookuphash[key2] );
  }

that would process items in that cell, and the neighbouring cells.  it
would be up to process_items to determine which point is actually the
nearest point.

this is fast to insert and remove items from the indexed tree... and
searching will be efficient depending on your range factor and the
number of neighbouring cells you search.

you can quicken up the search by making the process_items(etc) line
use the hash.find() instead of hash[] operator.


anyway, its not anything fancy like skd-tree or bkd-tree or even
kdtree, but that technique is easier to comprehend and simple to get
working.  all using standard STL containers.

see ya
Paul

2008/5/1 Eric Fowler <eric.fowler at gmail.com>:
> Well I am past the compilation hassles and have some test code running. I
> have noticed that while lookups are very fast, calling optimise() seems to
> take a long time (~10 seconds on a tree of 500,000 items). Since my
> application will involve a lot of 'churn' of items being added or deleted,
> this is a concern. Given that I want to find points in 2-space as fast as
> possible, and the efficient insertion and removal of points is an issue,
> what are my alternatives as far as:
>  - Perhaps using libkdtree in a more efficient manner, or
> - Using another data structure for this problem, or
> - Fixing the erase() code so it does not generate this problem, or
> - Fixing optimise() to run faster
>
> ?
>
>
>
> _______________________________________________
>  libkdtree-devel mailing list
>  libkdtree-devel at lists.alioth.debian.org
>  http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
>