Alternatives to libkdtree?

[Eric Fowler]

Thanks for the suggestion. It would not have occurred to me to use a hash
table to deal with ordered information. If I wanted to find the nearest
point, wouldn't I have to check for the nearest point in each of 9
neighboring squares, then sort? I don't have a firm req for that but it
would be nice to know.


I was thinking of taking a more conventional approach and storing the points
in two set<>'s, one sorted on x, the other on y (I have plenty of memory)
and using iterators through each set, one searching up, the other down. It's
not sophisticated but I should be able to get something working soon.

I am also looking at ANN. I assume you know what that is.

Thanks again

Eric

On Wed, Apr 30, 2008 at 11:04 PM, Paul Harris <paulharris at computer.org>
wrote:

> 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
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080501/bc60ca6c/attachment.htm