<div dir="ltr"><br><br><div class="gmail_quote">2008/10/21 Sylvain Bougerel <span dir="ltr"><<a href="mailto:sylvain.bougerel.devel@gmail.com">sylvain.bougerel.devel@gmail.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;">
<div class="Ih2E3d">On Tue, Oct 21, 2008 at 2:18 PM, Paul Harris <<a href="mailto:paulharris@computer.org">paulharris@computer.org</a>> wrote:<br>
> I agree, i just meant that the *current* kdtree uses euclidean distances<br>
> (right?), and that should be a template parameter.<br>
><br>
<br>
</div>The current uses euclidean distances.<br>
<br>
Besides there's something I wanted to know.<br>
<br>
Concerning the current euclidean distance calculation, in some cases,<br>
if you calculate a distance between some very far points, it might<br>
overflow and it would return a distance that is really wrong.<br>
<br>
<a href="http://www.gnu.org/software/gsl/manual/gsl-ref.html#index-euclidean-distance-function_002c-hypot-90" target="_blank">http://www.gnu.org/software/gsl/manual/gsl-ref.html#index-euclidean-distance-function_002c-hypot-90</a><br>
<br>
The link above points to a function that calculates distance in a way<br>
that avoids overflow (!):<br>
<br>
double<br>
gsl_hypot3(const double x, const double y, const double z)<br>
{<br>
double xabs = fabs(x);<br>
double yabs = fabs(y);<br>
double zabs = fabs(z);<br>
double w = GSL_MAX(xabs, GSL_MAX(yabs, zabs));<br>
<br>
if (w == 0.0)<br>
{<br>
return (0.0);<br>
}<br>
else<br>
{<br>
double r = w * sqrt((xabs / w) * (xabs / w) +<br>
(yabs / w) * (yabs / w) +<br>
(zabs / w) * (zabs / w));<br>
return r;<br>
}<br>
}<br>
<br>
<br>
I think we should do it this way too, but it only supports "float" and<br>
"double". Therefore, should we only provide a distance function for<br>
the type "float" and "double"?<br>
<br>
Also take not that it's a really slow calculation (because of all the division).<br>
<br>
Any suggestion concerning the other distance calculation that we should include?<br>
<font color="#888888"><br>
</font></blockquote><div><br><br>This is very interesting although not applicable to my environment ...<br>If you can catch double/float overflows (or at least check for them), then you could do the simple calculation first, and if it overflows, then do the slow version.<br>
<br>It could be included along with kdtree as an alternative distance calc that users can just plug into the template. ditto for any others that the current users have managed to figure out.<br></div></div><br>maybe follow up with the guy who was doing the distance-on-the-surface-of-the-earth? and other guys like him?<br>
<br></div>