Gosh you are right, I missed the problem of ints.<div>Strange, I think I would've noticed the smaller numbers before...</div><div><br><div>My comments on the test are still valid, I think this kdtree uses manhattan distance rather than euclidean distance when searching.</div>
<div><br></div><div>I adjusted the code in a similar way to what you have done, and pushed it to my repo here:</div><div><a href="https://github.com/paulharris/libkdtree">https://github.com/paulharris/libkdtree</a></div>
<div>
<br></div><div>If someone could please check what I've done, then pull it into the main tree, that would be great.</div><div><br></div><div>Note also that I don't use libkdtree anymore, I've switched to flann / nanoflann,</div>
<div>but compile fixes aren't hard to do so I did this little patch.</div><div><br></div><div>thanks again Andros for the report, I made a note in the git commit log.</div><div><br></div><div>cheers,</div><div>Paul</div>
<div><br></div><div><div><br><div class="gmail_quote">On 24 March 2013 18:51, AB <span dir="ltr"><<a href="mailto:androsb@optusnet.com.au" target="_blank">androsb@optusnet.com.au</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<br>
Greetings.<br>
<br>
<br>
This bug report concerns the file <br>
<br>
.../libkdtree/examples.<span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">/test_kdtree.cpp
.<br>
<br>
<br>
The "triplet" structure</span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"> has a
constructor that accepts three integers.<br>
<br>
The problem is that the "Walter"-related test at end of main()
function<br>
uses floating point values with the "triplet" constructor.<br>
As is, the precision of these </span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">floating point values
will be lost once the </span></span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">"triplet"</span> </span><br>
constructor implicitly converts these values to integers.<br>
<br>
This can be fixed by implementing "triplet", etc. as templates.<br>
<br>
<br>
Here's my solution to this problem ....<br>
<br>
<br>
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span></span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span>// Re: template declarations <br>
<br>
/* Andros, Sun 24 Mar 2013 09:13:42 EST<br>
Created a template version since need floating point support.<br>
Need a CTOR that takes floating point args, as realised by
g++-related<br>
warning ...<br>
"implicit conversion shortens 64-bit value into a 32-bit
value";<br>
i.e. avoid implicit [double --> int] conversion, avoid
loss of precision.<br>
*/<br>
<br>
</span><br>
<span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><br>
</span>template <typename VALUE_TYPE><br>
struct tripletT<br>
{<br>
typedef VALUE_TYPE value_type;<br>
<br>
value_type d[3];<br>
<br>
tripletT(value_type a, value_type b, value_type c)<br>
{<br>
d[0] = a;<br>
d[1] = b;<br>
d[2] = c;<br>
bool reg_ok = (registered.find(this) == registered.end());<br>
assert(reg_ok);<br>
registered.insert(this).second;<br>
}<br>
<br>
tripletT(const tripletT & x)<br>
{<br>
d[0] = x.d[0];<br>
d[1] = x.d[1];<br>
d[2] = x.d[2];<br>
bool reg_ok = (registered.find(this) == registered.end());<br>
assert(reg_ok);<br>
registered.insert(this).second;<br>
}<br>
<br>
~tripletT()<br>
{<br>
bool unreg_ok = (registered.find(this) != registered.end());<br>
assert(unreg_ok);<br>
registered.erase(this);<br>
}<br>
<br>
void write( ostream& os ) const<br>
{<br>
assert(registered.find(this) != registered.end());<br>
os << '(' << d[0] << ',' << d[1]
<< ',' << d[2] << ')';<br>
}<br>
<br>
double distance_to(tripletT const& x) const<br>
{<br>
double dist = 0;<br>
for (int i = 0; i != 3; ++i)<br>
dist += (d[i] - x.d[i]) * (d[i] - x.d[i]);<br>
return sqrt(dist);<br>
}<br>
<br>
inline value_type operator[](size_t const N) const<br>
{<br>
return d[N];<br>
}<br>
<br>
bool operator == (const tripletT& rhs) const<br>
{<br>
return d[0] == rhs.d[0] && d[1] == rhs.d[1] &&
d[2] == rhs.d[2];<br>
}<br>
<br>
<br>
bool operator != (const tripletT& rhs) const<br>
{<br>
return( ! operator==(rhs) );<br>
}<br>
}; // </span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">struct tripletT<></span><br>
<br>
<br>
// same as triplet, except with the values reversed.<br>
<br>
template <typename VALUE_TYPE><br>
struct alternate_tripletT<br>
{<br>
typedef VALUE_TYPE value_type;<br>
typedef tripletT<VALUE_TYPE> triplet;<br>
<br>
alternate_tripletT(const triplet & x)<br>
{<br>
d[0] = x.d[2];<br>
d[1] = x.d[1];<br>
d[2] = x.d[0];<br>
}<br>
<br>
inline value_type operator[](size_t const N) const<br>
{<br>
return d[2 - N];<br>
}<br>
<br>
value_type d[3];<br>
}; // </span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">struct
alternate_tripletT<></span><br>
<br>
<br>
typedef tripletT<int> triplet;<br>
typedef alternate_tripletT<int> alternate_triplet;<br>
<br>
<br>
template <typename TRIPLET_TYPE><br>
inline double tacT( TRIPLET_TYPE t, size_t k )<br>
{<br>
return t[k];<br>
}<br>
<br>
<br>
template <typename T><br>
ostream& operator << (ostream& os, const
tripletT<T>& o)<br>
{<br>
o.write( os );<br>
return( os );<br>
}<br>
</span><br>
<span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span></span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
// Re: updated code in main() using the above templates;
located at end of main()<br>
<br>
<br>
// Walter reported that the find_within_range() wasn't
giving results that were within<br>
// the specified range... this is the test.<br>
{<br>
typedef tripletT<double> triplet_d;<br>
<br>
<br>
typedef NAMESPACE_SEARCH_SORT::KDTree <<br>
3,<br>
triplet_d,<br>
pointer_to_binary_function<triplet_d, size_t,
double> ><br>
tree_type_d;<br>
<br>
<br>
tree_type_d tree( ptr_fun(tacT<triplet_d>) );<br>
tree.insert( triplet_d(28.771200, 16.921600, -2.665970) );<br>
tree.insert( triplet_d(28.553101, 18.649700, -2.155560) );<br>
tree.insert( triplet_d(28.107500, 20.341400, -1.188940) );<br>
tree.optimise();<br>
<br>
typedef deque<triplet_d> triplet_d_deque_t;<br>
<br>
triplet_d_deque_t vectors;<br>
triplet_d sv(18.892500, 20.341400, -1.188940);<br>
tree.find_within_range(sv, 10.0f, back_inserter(vectors));<br>
<br>
cout << endl <<<br>
"Test find_with_range( " << sv << ",
10.0f) found " << vectors.size() << " candidates."
<< endl;<br>
<br>
// double-check the ranges<br>
{<br>
triplet_d_deque_t::iterator last(vectors.end());<br>
</span></span></span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">double dist;<br>
</span></span></span> for (triplet_d_deque_t::iterator
v(vectors.begin()); v != last; ++v)<br>
{<br>
dist = sv.distance_to(*v);<br>
cout << " " << *v << " dist="
<< dist << endl;<br>
<br>
if (dist > 10.0f)<br>
cout << endl <<<br>
"This point is too far!" << endl <<<br>
"But that is by design, its within a 'box' with a
'radius' of 10, " << endl <<<br>
"not a sphere with a radius of 10" << endl;<br>
// Not a valid test, it can be greater than 10 if the
point is in the corners of the box.<br>
// assert(dist <= 10.0f);<br>
} // v<br>
}<br>
}<br>
</span></span></span><br>
<span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span></span><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;padding:0px;line-height:20px;text-transform:none;font-size:18.4px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px none;word-spacing:0px">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span></span></span></span><br>
<br>
<br>
<br>
Regards,<br>
<br>
Andros.<br>
<br>
<br>
</span><strong style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;font-weight:bold;padding:0px;line-height:20px;text-transform:none;font-size:18.399999618530273px;white-space:normal;margin:0px;font-family:Helvetica,arial,freesans,clean,sans-serif;border:0px;word-spacing:0px"></strong>
</div>
<br>_______________________________________________<br>
libkdtree-devel mailing list<br>
<a href="mailto:libkdtree-devel@lists.alioth.debian.org">libkdtree-devel@lists.alioth.debian.org</a><br>
<a href="http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel</a><br></blockquote></div><br></div></div></div>