Ближайший сосед - дерево кд - доказательство википедии

В записи в википедии для деревьев kd представлен алгоритм для поиска ближайшего соседа по дереву kd. Что я не понимаю, так это объяснение шага 3.2. Откуда вы знаете, что не существует более близкой точки только потому, что разница между координатой разделения точки поиска и текущего узла больше, чем разница между координатой разделения точки поиска и текущей наилучшей?

Поиск ближайшего соседа Анимация поиска NN с KD-деревом в 2D

Алгоритм ближайшего соседа (NN) стремится найти в дереве точку, ближайшую к заданной входной точке. Этот поиск можно эффективно выполнить, используя свойства дерева, чтобы быстро исключить большие части пространства поиска. Поиск ближайшего соседа в kd-дереве происходит следующим образом:

  1. Начиная с корневого узла, алгоритм рекурсивно перемещается вниз по дереву так же, как если бы точка поиска была вставлена ​​(т. Е. Идет вправо или влево в зависимости от того, больше или меньше точка текущего узла в разделить измерение).
  2. Как только алгоритм достигает конечного узла, он сохраняет точку этого узла как "текущий лучший"
  3. Алгоритм раскручивает рекурсию дерева, выполняя следующие шаги на каждом узле: 1. Если текущий узел ближе, чем текущий лучший, то он становится текущим лучшим. 2. Алгоритм проверяет, могут ли быть какие-либо точки на другой стороне плоскости разбиения, которые находятся ближе к точке поиска, чем текущая наилучшая. Концептуально это делается путем пересечения расщепляющейся гиперплоскости с гиперсферой вокруг точки поиска, радиус которой равен текущему ближайшему расстоянию. Поскольку все гиперплоскости выровнены по оси, это реализуется как простое сравнение, чтобы увидеть, меньше ли разница между координатой расщепления точки поиска и текущего узла, чем расстояние (общие координаты) от точки поиска до текущего лучшего. 1. Если гиперсфера пересекает плоскость, на другой стороне плоскости могут быть более близкие точки, поэтому алгоритм должен перемещаться вниз по другой ветви дерева от текущего узла в поисках более близких точек, следуя тому же рекурсивному процессу, что и весь поиск. 2. Если гиперсфера не пересекает плоскость расщепления, то алгоритм продолжает идти вверх по дереву, и вся ветвь на другой стороне этого узла удаляется.
  4. Когда алгоритм завершает этот процесс для корневого узла, поиск завершается.

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

Источник

2 ответа

Решение

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

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

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

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

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

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

Источник

Да, описание поиска NN (Nearest Neighbor) в KD Tree в Википедии немного сложнее. Это не помогает, что многие из лучших результатов поиска 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;
};
Источник
Другие вопросы по тегам