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. <br>
<br><br>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. <br>
<br>I am also looking at ANN. I assume you know what that is. <br><br>Thanks again<br><br>Eric<br>
<br><div class="gmail_quote">On Wed, Apr 30, 2008 at 11:04 PM, Paul Harris <<a href="mailto:paulharris@computer.org" target="_blank">paulharris@computer.org</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
if all you need to do is find a nearest point, you could try binning<br>
your points and then searching within a range of cells...<br>
<br>
eg: create a hash_map<> that uses a 'location' as a key. use<br>
boost::hash to help create the hashing function.<br>
<br>
calculate the location-key by dividing the item's location by a range<br>
factor and then rounding to an integer.<br>
the range factor something you would tune depending on how far you<br>
want to search for the nearest item. if you want to search 10 units<br>
away, then factor might be 10.<br>
<br>
then fill the hash. the key is rounded, the data is list or vector<br>
of pointers that point to the items in that cell.<br>
<br>
for (items::iterator item)<br>
lookuphash[ calc_key(*item) ].push_back( &*item );<br>
<br>
then to look up at location xy you would do...<br>
<br>
Key key = calc_key(xyz);<br>
for (int i = -1; i != 2; ++i)<br>
for (int j = -1; j != 2; ++j)<br>
{<br>
Key key2 ( key.x + i, key.y + j );<br>
process_items( lookuphash[key2] );<br>
}<br>
<br>
that would process items in that cell, and the neighbouring cells. it<br>
would be up to process_items to determine which point is actually the<br>
nearest point.<br>
<br>
this is fast to insert and remove items from the indexed tree... and<br>
searching will be efficient depending on your range factor and the<br>
number of neighbouring cells you search.<br>
<br>
you can quicken up the search by making the process_items(etc) line<br>
use the hash.find() instead of hash[] operator.<br>
<br>
<br>
anyway, its not anything fancy like skd-tree or bkd-tree or even<br>
kdtree, but that technique is easier to comprehend and simple to get<br>
working. all using standard STL containers.<br>
<br>
see ya<br>
Paul<br>
<br>
2008/5/1 Eric Fowler <<a href="mailto:eric.fowler@gmail.com" target="_blank">eric.fowler@gmail.com</a>>:<br>
<div><div></div><div>> Well I am past the compilation hassles and have some test code running. I<br>
> have noticed that while lookups are very fast, calling optimise() seems to<br>
> take a long time (~10 seconds on a tree of 500,000 items). Since my<br>
> application will involve a lot of 'churn' of items being added or deleted,<br>
> this is a concern. Given that I want to find points in 2-space as fast as<br>
> possible, and the efficient insertion and removal of points is an issue,<br>
> what are my alternatives as far as:<br>
> - Perhaps using libkdtree in a more efficient manner, or<br>
> - Using another data structure for this problem, or<br>
> - Fixing the erase() code so it does not generate this problem, or<br>
> - Fixing optimise() to run faster<br>
><br>
> ?<br>
><br>
><br>
><br>
</div></div>> _______________________________________________<br>
> libkdtree-devel mailing list<br>
> <a href="mailto:libkdtree-devel@lists.alioth.debian.org" target="_blank">libkdtree-devel@lists.alioth.debian.org</a><br>
> <a href="http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel</a><br>
><br>
><br>
</blockquote></div><br>