<br><br><div class="gmail_quote">2009/1/29 Walter Keiner <span dir="ltr"><<a href="mailto:walter.keiner@googlemail.com">walter.keiner@googlemail.com</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello Paul,<br><br>sorry for my late answer but I have been busy too. <br><br>Do you have to take a box for that test? Maybe you could use a sphere instead. <br></blockquote><div><br>The reason is that each dimension is tested separately... this means it can be done quickly via (pseudo-code)<br>
<br>for (d in dimensions)<br> if not ( box[d].min <= point[d] <= box[d].max )<br> is not valid candidate<br><br>one of those dimensions doesn't need to be tested as it would've been just tested at that level (a minor optimisation).<br>
<br><br>to do a sphere test, you need to do more math, less tests...<br>mapped = point - box.origin<br>dist = 0<br>for (d in dimensions)<br>
dist += mapped[d] * mapped[d]<br>if ( sqrt(dist) <= max_dist)<br> is valid candidate<br> <br>maybe that would be faster than 2 tests per dimension... the sqrt can be factored out<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>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().<br>
</blockquote><div><br>true. an evolved framework is on the cards but i'm too busy atm to do any major work.<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>I need a test and at the moment I check all values from find_within_range().<br></blockquote><div><br>you can do it right now with visit_within_range()<br><br>pseudo-code<br><br>struct exact_check<br>{<br> exact_check( OutIterator out, centre, radius ) { store them in local vars; }<br>
<br> // note, not sure if operator is called with the dereferenced value, or<br> // with the tree-iterator<br> void operator()( Node const& n ) const<br> {<br> if ( n within (centre,radius) )<br> *out++ = n;<br>
}<br>};<br><br></div></div>so the visitor does the extra test and does the work of filling an output iterator.<br>course, it could also do more work and bypass the iterator completely - more efficient.<br><br>see ya<br>
Paul<br><br>