nearest_neighbour_search()

template<uint32_t K>

auto scl::kd_tree< K >::nearest_neighbour_search ( const item & point, const item & condition ) const -> item

inline

Search for a nearest point in the kd_tree. Traverse the tree as in a normal search to find the leaf node closest to the query point. Unwind the recursion, considering at each step whether there could be any points on the other side of the splitting plane that are closer to the query point than the current best. If there could be, recurse down the other branch, adding any closer points found to the current best. The final best point is the nearest neighbor.

Parameters

[in]	point	Searched point in k d.
[in]	condition	allowed distance for neighbours.

Returns

Returns nearest point.

Definition at line 629 of file KDTree.h.

    {
        std::vector<kd_tree<K>::item> rangePoints;
        range_search_recursive(m_Root, point, condition, rangePoints, 0);
 
        if (rangePoints.size() == 0) return {};
 
        int nearIndex = -1;
        float nearRate = 1E11;
        for (int i = 0; i < rangePoints.size(); i++)
        {
            float rate = 0;
            for (int j = 0; j < K; j++)
            {
                rate += std::abs(rangePoints[i][j] - point[j]);
            }
            if (rate <= nearRate)
            {
                nearRate = rate;
                nearIndex = i;
            }
        }
 
        return rangePoints[nearIndex];
    }