Accuracy of libkdtree

[Paul Harris]

2009/1/29 Walter Keiner <walter.keiner at googlemail.com>

> Hello Paul,
>
> sorry for my late answer but I have been busy too.
>
> Do you have to take a box for that test? Maybe you could use a sphere
> instead.
>

The reason is that each dimension is tested separately... this means it can
be done quickly via (pseudo-code)

for (d in dimensions)
  if not ( box[d].min <= point[d] <= box[d].max )
    is not valid candidate

one of those dimensions doesn't need to be tested as it would've been just
tested at that level (a minor optimisation).


to do a sphere test, you need to do more math, less tests...
mapped = point - box.origin
dist = 0
for (d in dimensions)
    dist += mapped[d] * mapped[d]
if ( sqrt(dist) <= max_dist)
   is valid candidate

maybe that would be faster than 2 tests per dimension... the sqrt can be
factored out


> I think that maybe two methods would be good. As you said it has been
> always like that, there might be people who just need an approximate check.
> The name of the method find_within_range() implies a mathematical
> correctness. So it would be great if there would be a check. Maybe you can
> use the fast algorithm without check in a method like find_approximately().
>

true. an evolved framework is on the cards but i'm too busy atm to do any
major work.


>
> I need a test and at the moment I check all values from
> find_within_range().
>

you can do it right now with visit_within_range()

pseudo-code

struct exact_check
{
  exact_check( OutIterator out, centre, radius ) { store them in local vars;
}

  // note, not sure if operator is called with the dereferenced value, or
  // with the tree-iterator
  void operator()( Node const& n ) const
  {
     if ( n within (centre,radius) )
       *out++ = n;
  }
};

so the visitor does the extra test and does the work of filling an output
iterator.
course, it could also do more work and bypass the iterator completely - more
efficient.

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