Cuál es el pseudo código de alto nivel para buscar todos los vecinos dentro de un radio r de un punto de consulta en un árbol kd.

Esta página tiene descripciones de alto nivel y seudocódigo para la mayoría de las operaciones que se pueden realizar en un kd-tree.

Por ejemplo, describe cómo inicializarlo:

function kdtree (lista de puntos pointList, entero depth)
{
    // Seleccione el eje en función de la profundidad para que el eje recorra todos los valores válidos
    var entero axis := depth mod k;

<pre><code>// Ordenar la lista de puntos y elegir la mediana como elemento pivote
seleccionar mediana por eje de pointList;

// Crear nodo y construir subárbol
nodo.location := mediana;
nodo.leftChild := kdtree(puntos en pointList antes de la mediana, depth+1);
nodo.rightChild := kdtree(puntos en pointList después de la mediana, depth+1);
return nodo;
</code></pre>

<p>}

Tenga en cuenta que lo anterior no es un lenguaje de programación específico, solo es seudocódigo, lo que estoy buscando (quiero entender el algoritmo, no necesariamente implementarlo).

Sin embargo, esa página no explica en absoluto cómo encontrar todos los vecinos dentro de un radio de un punto de consulta, pero esta es una operación común para los kd-trees.

Dicho de otra manera, suponga que se tiene un kd-tree ya inicializado en algún lenguaje mágico. Se podría hacer lo siguiente para encontrar el conjunto de todos los puntos en el árbol que están a 0.1 unidades de distancia del punto de consulta (pi, e, epsilon)

kd_tree.find_neighbours((pi, e, epsilon), 0.1)

Si quisiéramos el punto más cercano en lugar de todos los puntos dentro de un radio, podríamos seguir los pasos descritos en la sección Búsqueda del vecino más cercano. Sin embargo, ese es un objetivo diferente y un algoritmo diferente.

¿Cuál es el algoritmo para encontrar puntos dentro de un radio en un kd-tree?