ближайший сосед - k-d tree - wikipedia proof

Внимательно посмотрите на 6-й кадр анимации на этой странице.

Поскольку алгоритм возвращается к рекурсии, возможно, что есть более близкая точка на другой стороне гиперплоскости, на которой она находится. Мы проверили одну половину, но на другой половине может быть еще более близкая точка.

Что ж, оказывается, иногда можно сделать упрощение. Если невозможно найти точку на другой половине ближе, чем наша текущая лучшая (ближайшая) точка, то мы можем полностью пропустить эту половину гиперплоскости. Это упрощение показано на 6-м кадре.

Чтобы выяснить, возможно ли это упрощение, нужно сравнить расстояние от гиперплоскости до места поиска. Поскольку гиперплоскость выровнена по осям, самая короткая линия от нее до любой другой точки будет линией вдоль одного измерения, поэтому мы можем сравнить только координаты измерения, которое разделяет гиперплоскость.

Если он находится дальше от точки поиска до гиперплоскости, чем от точки поиска до ближайшей к вам текущей точки, то нет причин искать за этой координатой разделения.

Даже если мое объяснение не поможет, графическое изображение поможет. Удачи с проектом!

Да, описанию поиска NN (ближайшего соседа) в дереве KD в Википедии немного сложно следовать. Не помогает то, что многие лучшие результаты поиска Google по поиску NN KD Tree просто ошибочны!

Вот код на C ++, чтобы показать вам, как это сделать правильно:

template <class T, std::size_t N>
void KDTree<T,N>::nearest (
    const const KDNode<T,N> &node,
    const std::array<T, N> &point, // looking for closest node to this point
    const KDPoint<T,N> &closest,   // closest node (so far)
    double &minDist,
    const uint depth) const
{
    if (node->isLeaf()) {
        const double dist = distance(point, node->leaf->point);
        if (dist < minDist) {
            minDist = dist;
            closest = node->leaf;
        }
    } else {
        const T dim = depth % N;
        if (point[dim] < node->splitVal) {
            // search left first
            nearest(node->left, point, closest, minDist, depth + 1);
            if (point[dim] + minDist >= node->splitVal)
                nearest(node->right, point, closest, minDist, depth + 1);
        } else {
            // search right first
            nearest(node->right, point, closest, minDist, depth + 1);
            if (point[dim] - minDist <= node->splitVal)
                nearest(node->left, point, closest, minDist, depth + 1);
        }
    }
}

API для поиска NN в дереве KD:

// Nearest neighbour
template <class T, std::size_t N>
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const {
    const KDPoint<T,N> closest;
    double minDist = std::numeric_limits<double>::max();
    nearest(root, point, closest, minDist);
    return closest;
}

Функция расстояния по умолчанию:

template <class T, std::size_t N>
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) {
    double d = 0.0;
    for (uint i = 0; i < N; ++i) {
        d += pow(p1[i] - p2[i], 2.0);
    }
    return sqrt(d);
}

Изменить: некоторые люди также просят помощи со структурами данных (а не только с алгоритмом NN), поэтому вот что я использовал. В зависимости от вашей цели вы можете немного изменить структуры данных. (Примечание: но вы почти наверняка не хотите изменять алгоритм NN.)

KDPoint класс:

template <class T, std::size_t N>
class KDPoint {
    public:
        KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { };
        virtual ~KDPoint<T,N> () = default;
        std::array<T, N> point;
};

Класс KDNode:

template <class T, std::size_t N>
class KDNode
{
    public:
        KDNode () = delete;
        KDNode (const KDNode &) = delete;
        KDNode & operator = (const KDNode &) = delete;
        ~KDNode () = default;

        // branch node
        KDNode (const T                       split,
                std::unique_ptr<const KDNode> &lhs,
                std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { };
        // leaf node
        KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { };

        bool isLeaf (void) const { return static_cast<bool>(leaf); }

        // data members
        const T                                   splitVal;
        const std::unique_ptr<const KDNode<T,N>>  left, right;
        const std::shared_ptr<const KDPoint<T,N>> leaf;
};

Класс KDTree: (Примечание: вам нужно добавить функцию-член для построения / заполнения вашего дерева.)

template <class T, std::size_t N>
class KDTree {
    public:
        KDTree () = delete;
        KDTree (const KDTree &) = delete;
        KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { };
        KDTree & operator = (const KDTree &) = delete;
        ~KDTree () = default;

        const KDPoint<T,N> nearest (const std::array<T, N> &point) const;

        // Nearest neighbour search - runs in O(log n)
        void nearest (const std::unique_ptr<const KDNode<T,N>> &node,
                      const std::array<T, N> &point,
                      std::shared_ptr<const KDPoint<T,N>> &closest,
                      double &minDist,
                      const uint depth = 0) const;

        // data members
        const std::unique_ptr<const KDNode<T,N>> root;
};