`Octree.findNearestNeighbour` doesn't always return the nearest point?

[ChrisDenham]

Firstly, thanks for sharing your code.

I have been experimenting with this implementation (currently at f433a92c76c05ea94a97d3cceebbd040cdc0b8d8) with a view to using it to speed up searching for nearby 3D points in my application. However, I'm puzzled by the result of my very simple test which seems to return the incorrect point when calling Octree.findNearestNeighbour. My test shown below has been reduced and could not really be simpler as it adds only two points (0, 2, 3) and (0, 4, 5) and tests which is nearer to (0, 2, 4). You can see that the first point has a distance of 1 from (0, 2, 4) but the second point is at distance sqrt(5), and therefore it seems to me that the findNearestNeighbour function should return the first point, not the second (even accounting for integer rounding issues)?

If this is a bug, any thoughts on how to fix it? If this is not a bug, what am I missing?

Octree<unsigned> octree(8);
octree.insert(0, 2, 3, 0);
octree.insert(0, 4, 5, 1);

unsigned found_x;
unsigned found_y;
unsigned found_z;
auto leaf = octree.findNearestNeighbour(0, 2, 4, found_x, found_y, found_z);
assert(found_x == 0 && found_y == 2 && found_z == 3);
assert(leaf->value() == 0);

Thanks.

[mwarning]

Hi,

thanks for raising this issue. I will try to take a look later. This indeed smell like a bug.

[ChrisDenham]

Thanks. BTW. in case it's useful, my suspicion is that the issue is related to integer rounding for the search box bounds that happens here:

// Search box volume.
int x_min, x_max;
int y_min, y_max;
int z_min, z_max;
....

const int r = std::sqrt(sq_distance) + 1.0;

x_min = pos_x - r;
x_max = pos_x + r;
y_min = pos_y - r;
y_max = pos_y + r;
z_min = pos_z - r;
z_max = pos_z + r;

My first thought was, should the + 1.0 be + 0.5 for rounding to nearest int, but that didn't help.

My second thought was that the box volume needed to be floats or doubles, and although changing that (snippet below) fixed the problem for this specific test, I'm not 100% sure it was a good general fix, or how much impact that would have on performance:

// Search box volume.
float x_min, x_max;
float y_min, y_max;
float z_min, z_max;
....

const float r = std::sqrt(sq_distance);

x_min = pos_x - r;
x_max = pos_x + r;
y_min = pos_y - r;
y_max = pos_y + r;
z_min = pos_z - r;
z_max = pos_z + r;

[mwarning]

Thanks for the suggestion. But I would like to put in some time to figure out the exact cause and do some benchmarks, of course.

[ChrisDenham]

OK, thank you. My suggestion was more of a hopefully helpful hint, but of course, it may be completely misleading information as I didn't drill too deep trying to understand what was going on. Cheers.