K-d деревья: алгоритм поиска ближайших соседей

Таково мое понимание этого.: 1. Рекурсия вниз по дереву, принимая левое или правое поддерево в зависимости от того, будет ли элемент лежать в левом или правом поддереве, если он существует. 2. Установите CURRENT_BEST в качестве первого конечного узла, которого вы достигнете. 3. При рекурсии назад проверьте, находится ли элемент ближе к разделяющей гиперплоскости, чем к CURRENT_BEST. Если это так, установите CURRENT_BEST в качестве текущего узла.

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

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

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

3 4
algorithm kdtree nearest-neighbor

3 ответа:

Шаг 4 - это " еще " в шаге 3, что вы делаете, если плоскость ближе, чем точка. Просто потому, что найденная вами точка будет находиться в том же прямоугольнике, что и точка, для которой вы находите соседа, не означает, что она ближе всего.

Представьте себе следующий сценарий: у вас есть две точки в вашем KD-дереве, A и B. A находится в середине его прямоугольника, в то время как B находится сразу за краем, в секционированной области рядом с областью A. Если вы теперь ищете ближайший сосед к точке C, который находится прямо рядом с B, но оказывается с другой стороны края и в области раздела A, ваша первая точка, которую вы выберете, будет A из-за начальной глубины первого поиска, который выбирает то, что будет в том же разделе, что и ваша точка поиска. Однако B на самом деле ближе, поэтому, даже если вы выбрали A, вам нужно проверить, является ли B ближе, иначе ваше KD-дерево на самом деле не даст вам правильных результатов.

Хороший способ визуализировать это-нарисовать его:

A-------------C--|--B

A-первая точка, которую мы нашли в DFS, C-наша точка, которую мы хотим видеть ближайшим соседом, B-фактический ближайший сосед, | - наша расщепленная плоскость.

Другой способ думать об этом-нарисовать круг с радиусом dist(A,C) вокруг точки C. Если какие-либо другие прямоугольники имеют какую-либо часть себя, попадающую в эту окружность, то есть шанс, что они содержат точку, которая может быть ближе к C, чем A, поэтому они должны быть проверены. Если вы сейчас найдете б, вы можете уменьшить радиус вашего круга (потому что B ближе) так, чтобы меньше прямоугольников имели шанс пересечься, и как только вы проверили все прямоугольники, которые пересекаются с вашим кругом (уменьшая радиус круга, как вы находите более близких соседей), вы можете окончательно сказать, что нет более близких точек.

7

Я написал базовую реализацию C++ на github. Он имеет как итеративную, так и рекурсивную версию.

2
function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtrees
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}
-4