KNN not finding the nearest neighbour with small K about octree

[LeweC]

Works great!
I am happy to help and thank you for your quick fixes.
I will close the issue again :)

[attcs]

Hi!
Thank you for the detailed description, it was very helpful! I pushed a bugfix, I hope you won't have any other problems with my library.

[LeweC]

Great!
I have also tested some different configurations and larger sample sizes, it seems to be fixed.
I will close the issue now.

Thanks for the quick work!

[LeweC]

Sorry I spoke too soon.

It seems that the bug persists in higher dimensions. As I wrote above, my quick tests with the quadtree went fine.

Here is another example where I get this error and a large K seems to fix it. This time for 6 dimensions:

void test_setup()
{
    array<double, 6> point1 = {50.2232, 0.276687, 37.7662, 41.2776, 26.3818, 74.0284};
    array<double, 6> point2 = {35.8946, 83.7503, 97.1127, 47.2895, 40.9232, 83.7666};
    array<double, 6> point3 = {33.3541, 63.0669, 3.86075, 47.7923, 19.8039, 87.5608};
    array<double, 6> point4 = {89.0684, 67.3278, 50.867, 49.8193, 72.6692, 54.0271};
    array<double, 6> point5 = {75.7099, 53.1241, 39.624, 40.4669, 13.6433, 88.6247};
    array<double, 6> point6 = {43.7641, 93.7985, 68.8286, 9.71882, 2.16644, 12.1925};
    array<double, 6> point7 = {82.5195, 30.6964, 71.0556, 48.4744, 99.2295, 70.4137};
    array<double, 6> point8 = {28.4568, 37.8366, 74.8597, 27.897, 60.6816, 0.247821};
    array<double, 6> point9 = {58.3617, 17.0165, 15.1021, 70.9832, 22.5325, 34.8085};
    array<double, 6> point10 = {33.1004, 72.6729, 35.7043, 35.2888, 94.9917, 17.652};
    array<double, 6> point11 = {80.9693, 7.41406, 2.18394, 40.2606, 1.63274, 65.8996};
    array<double, 6> point12 = {88.4851, 73.8366, 55.0264, 77.6467, 61.6751, 33.7444};
    array<double, 6> point13 = {48.1777, 90.1285, 75.9069, 49.1867, 39.7186, 74.2862};
    array<double, 6> point14 = {68.0826, 73.0622, 7.85933, 60.8879, 41.3229, 16.6928};
    array<double, 6> point15 = {19.1693, 49.1172, 91.055, 52.5548, 16.2326, 0.610075};
    array<double, 6> point16 = {19.3085, 81.9363, 55.8924, 1.77161, 29.4124, 72.3873};
    array<double, 6> point17 = {57.8801, 28.3918, 45.7062, 92.1774, 0.742745, 29.0499};
    array<double, 6> point18 = {74.2952, 84.6691, 46.3357, 76.7894, 68.8394, 24.1707};
    array<double, 6> point19 = {0.199418, 93.2845, 94.9628, 38.2295, 82.1998, 59.2499};
    array<double, 6> point20 = {68.4689, 0.261607, 75.5001, 58.427, 55.4243, 18.7392};
    array<double, 6> point21 = {53.9164, 95.4966, 59.657, 71.0292, 82.4362, 53.9452};


    vector<array<double, 6>> poses = {
        point1,
        point2,
        point3,
        point4,
        point5,
        point6,
        point7,
        point8,
        point9,
        point10,
        point11,
        point12,
        point13,
        point14,
        point15,
        point16,
        point17,
        point18,
        point19,
        point20,
        point21,
        };

    array<double, 6> search_point = {78.8658, 64.0361, 18.7755, 61.4618, 14.3312, 40.0196};

    std::array<double, 6> inspection_space_min = {0.0, 0.0, 0.0, 0.0, 0.0, 0.0};
    std::array<double, 6> inspection_space_max = {100.0, 100.0, 100.0, 100.0, 100.0, 100.0};
    OrthoTree::BoundingBoxND<6> inspection_space;
    inspection_space.Min = inspection_space_min;
    inspection_space.Max = inspection_space_max;
    //Standard Tree
    auto tree = TreePointND<6>();
    tree.Create(tree, poses, 10, inspection_space);

    vector<array<double, 6>> m_data = poses;

    auto neighbors = tree.GetNearestNeighbors(search_point, 1, m_data);


    using AD = OrthoTree::AdaptorGeneral<2, array<double, 6>, OrthoTree::BoundingBox2D>;
    auto const itMin = std::ranges::min_element(poses, [&search_point](auto const& lhs, auto const& rhs) { return AD::distance2(lhs, search_point) < AD::distance2(rhs, search_point); });
    auto real_tree_distance = std::distance(poses.begin(), itMin);

    if (neighbors[0] != real_tree_distance)
    {
        std::cout << "real distance ID is: " << real_tree_distance<< std::endl;
        std::cout << "Tree found distance ID: " << neighbors[0]<< std::endl;
    }
}

I also used the same method to check the results as your unit tests, instead of my own euclidean distance method.

Btw. in your most recent commit for the unit test

Octree/unittests/general.tests.cpp

Line 1747 in 6dba0d3

autoc itMin = std::ranges::min_element(poses, [&search_point](autoc& lhs, autoc& rhs) { return AD::distance2(lhs, search_point) < AD::distance2(rhs, search_point); });

Shouldn't distance2 be distance? Because that is the distance metric used by the PointTree.
For example:

Octree/octree.h

Line 1781 in 6dba0d3

setEntity.insert({ { AD::distance(pt, vpt[id]) }, id });

Seems to me that its the same bug, so maybe its a problem with the same if codindition and break. But I am not sure why it seems to be fixed for quadtrees.

[attcs]

Hi!
It was a different problem. As I checked the example I found out, if the given depth of the tree was set to lower (6 instead of 10), it worked correctly. (The recommended value of depth is 3-5 in a usual case., otherwise the deep hierarchy could slow down the searches.)

I found the bug in the MortonEncode function: uint32_t is the grid id variable, which could lead to integer-overflow during the shifting (with this dimension number and high depth), consequently resulted erroneous Morton-ids.

distance2 is almost the same metric, just the sqrt is not applied, this does not change on the order.

Thank you very much for your help, I really appreciate it.