<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
Greetings.<br>
<br>
<br>
This bug report concerns the file <br>
<br>
.../libkdtree/examples.<span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color: rgb(0,
0, 0); font-family: Helvetica,arial,freesans,clean,sans-serif;
font-size: 18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; background-color: rgb(255, 255, 255);">/test_kdtree.cpp
.<br>
<br>
<br>
The "triplet" structure</span><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color: rgb(0,
0, 0); font-family: Helvetica,arial,freesans,clean,sans-serif;
font-size: 18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; background-color: rgb(255, 255, 255);"> 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 class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color: rgb(0,
0, 0); font-family: Helvetica,arial,freesans,clean,sans-serif;
font-size: 18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; background-color: rgb(255, 255, 255);"><span
class="final-path" style="margin: 0px; padding: 0px; border: 0px
none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);">floating point values
will be lost once the </span></span><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color: rgb(0,
0, 0); font-family: Helvetica,arial,freesans,clean,sans-serif;
font-size: 18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; background-color: rgb(255, 255, 255);"><span
class="final-path" style="margin: 0px; padding: 0px; border: 0px
none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent:
0px; text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);">"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 class="final-path" style="margin: 0px; padding: 0px;
border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing: normal;
line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span></span><span class="final-path" style="margin: 0px;
padding: 0px; border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing: normal;
line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<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 class="final-path" style="margin: 0px; padding: 0px; border:
0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing: normal;
line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><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 class="final-path" style="margin: 0px;
padding: 0px; border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing: normal;
line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);">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 class="final-path" style="margin: 0px;
padding: 0px; border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing: normal;
line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);">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 class="final-path" style="margin: 0px; padding: 0px; border:
0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing: normal;
line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span><span class="final-path" style="margin: 0px; padding: 0px;
border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent:
0px; text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span></span><span class="final-path" style="margin: 0px;
padding: 0px; border: 0px none; color: rgb(0, 0, 0);
font-family: Helvetica,arial,freesans,clean,sans-serif;
font-size: 18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; background-color: rgb(255, 255, 255);"><span
class="final-path" style="margin: 0px; padding: 0px; border:
0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent:
0px; text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<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 class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color: rgb(0,
0, 0); font-family: Helvetica,arial,freesans,clean,sans-serif;
font-size: 18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; background-color: rgb(255, 255, 255);"><span
class="final-path" style="margin: 0px; padding: 0px; border: 0px
none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent:
0px; text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);"><span
class="final-path" style="margin: 0px; padding: 0px; border:
0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size:
18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align:
start; text-indent: 0px; text-transform: none; white-space:
normal; word-spacing: 0px; background-color: rgb(255, 255,
255);"><span class="final-path" style="margin: 0px; padding:
0px; border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size:
18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px; background-color:
rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none;
color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size:
18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);">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 class="final-path" style="margin: 0px; padding: 0px; border:
0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing: normal;
line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="final-path"
style="margin: 0px; padding: 0px; border: 0px none; color:
rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size: 18.4px;
font-style: normal; font-variant: normal; letter-spacing:
normal; line-height: 20px; text-align: start; text-indent:
0px; text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);"><span
class="final-path" style="margin: 0px; padding: 0px; border:
0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size:
18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align:
start; text-indent: 0px; text-transform: none; white-space:
normal; word-spacing: 0px; background-color: rgb(255, 255,
255);">// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span><span class="final-path" style="margin: 0px; padding:
0px; border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size:
18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align:
start; text-indent: 0px; text-transform: none; white-space:
normal; word-spacing: 0px; background-color: rgb(255, 255,
255);"><span class="final-path" style="margin: 0px; padding:
0px; border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size:
18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px; background-color:
rgb(255, 255, 255);">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span></span><span class="final-path" style="margin: 0px;
padding: 0px; border: 0px none; color: rgb(0, 0, 0);
font-family: Helvetica,arial,freesans,clean,sans-serif;
font-size: 18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align:
start; text-indent: 0px; text-transform: none; white-space:
normal; word-spacing: 0px; background-color: rgb(255, 255,
255);"><span class="final-path" style="margin: 0px; padding:
0px; border: 0px none; color: rgb(0, 0, 0); font-family:
Helvetica,arial,freesans,clean,sans-serif; font-size:
18.4px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px; background-color:
rgb(255, 255, 255);">//
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
</span></span></span></span><br>
<br>
<br>
<br>
Regards,<br>
<br>
Andros.<br>
<br>
<br>
</span><strong class="final-path" style="margin: 0px; padding: 0px;
border: 0px; font-weight: bold; color: rgb(0, 0, 0); font-family:
Helvetica, arial, freesans, clean, sans-serif; font-size:
18.399999618530273px; font-style: normal; font-variant: normal;
letter-spacing: normal; line-height: 20px; orphans: auto;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; widows: auto; word-spacing: 0px;
-webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255);"></strong>
</body>
</html>