Estructura de datos de particionamiento de espacio binario para espacio 2D Donut

Question

Tengo un mapa 2D que se envuelve en los bordes. Entonces, si te mueves fuera del borde derecho, volverás a aparecer en el lado izquierdo del mapa. Del mismo modo con los otros tres bordes.

Esto es un problema hereditario para el KDTree que utilizo para encontrar elementos en el rango de puntos. Normalmente, usted verificará si la hiper esfera choca con el hiperplano para ver si debe continuar buscando en el otro lado del árbol, pero esta verificación no funciona con bordes envolventes.

¿Hay alguna manera de modificar el Árbol KD para que funcione con espacios donut 2D?

Answer 1

Un quadtree es un árbol KD con 4 hojas. Un quadtree no ayuda a envolver porque su estructura de datos es una envoltura en sí misma. Solo necesitas usar un quadtree 2x de tu estructura.

Answer 2

Jitamaro sugirió pero no explicó un método basado en un quadtree "2x size". Es una sugerencia razonable, excepto que el quadtree usa cuatro veces más nodos que dos, como explicaré a continuación antes de proponer tentativamente un método alternativo.

Supongamos cada (x, y) de coordenadas tiene -.5 < x <= .5 y -.5 < y <= .5 y siempre que j, k son números enteros, punto (x + j, y + k) es idéntico con el punto (x, y). Deje que quadtree T cubra puntos con coordenadas en el rango -1 < x,y <= 1. Cada vez que agrega un artículo en (x, y) a T, donde -.5 < x,y <= .5, deje x' = {x-1 si x>0 else x+1}, y y' = {y-1 si y>0 else y+1}. También agregue el artículo en (x, y '), (x', y ') y (x', y). [Cuando elimine puntos más tarde, vuelva a calcular (x ', y') y elimínelos también.] Es fácil ver que las búsquedas de punto más cercano funcionarán correctamente, siempre que cualquier coordenada de búsqueda fuera del intervalo (-.5,.5] se ajuste correctamente.

Si el número cuádruple de nodos es decisivo, tenga en cuenta que si las coordenadas descritas anteriormente se usan en subárboles superiores al nivel k=3, y las coordenadas relativas se almacenan por debajo del nivel k, debería ser posible mantener solo copias de subárboles por debajo del nivel k. Es decir, cada subárbol en el nivel k tendría cuatro padres. (No he pensado en esto lo suficiente como para saber si esto funciona totalmente; editaré la respuesta si encuentro que no.)

Answer 3

La estructura de datos no tiene que cambiar, pero sí el procedimiento de búsqueda. Represente cada punto por coordenadas (x, y) en [0, w) * [0, h), donde w es el ancho del mapa, h es la altura y * indica un producto cartesiano. Almacene estos puntos en un árbol KD normal.

La primitiva fundamental para buscar un árbol KD es, dado un punto (x, y) y un rectángulo [a, b] * [c, d], determinar la distancia (al cuadrado) del punto al rectángulo. Normalmente esto es g (x, a, b) + g (y, c, d) , donde

g(z, e, f) = e - z if z < e 
      0  if e <= z <= f 
      z - f if f < z 

es la distancia unidimensional de z para [e, f]. En un espacio toroidal, modificamos g ligeramente para tener en cuenta el envolvente.

g(z, e, f, v) = min(e - z, (z + v) - f) if z < e 
       0      if e < z < f 
       min(z - f, (e + v) - z) if f < z. 

y la distancia al cuadrado es g (x, a, b, w) + g (y, c, d, h) . Espero que los tiempos de ejecución sean comparables para esta variante.(Reharía las recurrencias, pero el peor caso para árboles KD normales es mucho peor que practicar la mayoría de las veces - O (n ^1/2) para identificar el vecino más cercano en 2D entre n puntos)