Tree structures -- especially binary tree structures -- are frequently
a bad choice in J.
Personally, if I were working with spatial data in J, I'd probably
start with something like this:
NB. example arbitrary set of points:
points=: ?.20 3$0
prepad=: $&__@,~@{:@$, ], $&_@,~@{:@$
searchable=: /:~@:((|."0 1) ,:^:(2 - #@$))"0 2~ i.@{:@$
SP=: searchable prepad points
In other words: make n copies of the list of points (where n is the
number of dimensions) and sort each list so that it can be binary
searched along one of those dimensions.
Of course, it's not that simple. To find the nearest point, you need
to search a volume which includes your candidate points. So, in the
worst case (most points equidistant from the point you are checking)
you wind up searching the entire data structure.
I've assumed, here, that once we've done a binary search to find a
close match to the point we are looking for that it's worth searching
the n nearest points in each direction from that match (where n is the
number of dimensions). So this means an initial search of n*(1+n)
points (n lists of candidates each containing 1+n points). We need to
extend our search if any of the 2n points bounding each of the n lists
of candidates has a coordinate distance from the point we are looking
for which is closer than our closest candidate.
This might sound significantly less efficient than a kd-tree, but we
need to keep in mind that the kd-tree (or r* tree) has significant
costs from cache misses and from pipeline busting.
That said, there are a few other tricks that might be needed. For
example, if you are incrementally building the structure, adding to
sorted lists is inefficient. You can work around this issue by
maintaining multiple instances of the logical structure and searching
both (or all) of them and then picking the best result (for example).
Then occasionally you find some time to merge them together.
That said, I have not had time to draft up a real sample. (The
project I am currently working on releases this weekend, and in my
"spare" time I'm taking a class, which leaves me without much time for
fun stuff like this.)
I hope this helps,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
