Skip to content

Adding kd tree test with sample dataset

Caitlin Ross requested to merge caitlin.ross/diy:new-kd-tree-test into master

This MR adds a test that recreates an issue we've encountered with DIY's kd tree, where we get the following assert error:

Assertion failed: (0), function find_split, file diy/detail/algorithms/kdtree.hpp, line 548.

I've created a test program for this, along with a sample dataset. When we increase the number of blocks, it becomes more likely to hit the failure. We've had some success with changing the bins, but it doesn't always help. In the case of this test, 2 and 4 blocks pass (regardless of number of bins), but using 8 or more blocks fails.

I'm thinking that it is an issue with precision. In the datasets where we get this error, there are regions where points are dense. So I think when you get a dense enough area, the blocks being created in that area are small enough that single precision isn't good enough for comparing the changed and original bounds in KDTreePartition::find_split.

Merge request reports