Cuándo usar árboles Kd?

Question

Estaba leyendo acerca de Kd-Trees el otro día y estaba buscando una situación concreta/simple donde una estructura de datos así podría ser útil.

¿Alguien tiene un ejemplo así?

Gracias,

Answer 1

Los he utilizado como un medio eficaz para encontrar los vecinos más cercanos de un punto dado de aprendizaje automático.

Answer 2

Se utilizan en raytacing para dividir una escena en un par de cajas. Acelera las colisiones porque si un rayo no colisiona con el cuadro delimitador, seguramente no colisiona con su contenido.

Answer 3

VTK tiene uno: http://www.vtk.org/doc/nightly/html/classvtkKdTree.html por ejemplo.

Eche un vistazo a funciones como "FindClosestPoint". La clase toma un tiempo comparativamente largo para construir dado un gran conjunto de puntos de entrada. Pero después de que se construye el árbol, funciones como esta funcionan muy rápido.

Answer 4

Los usé en un proyecto de fijación de precios. El objetivo era encontrar el mejor precio que coincidiera con múltiples criterios.

Answer 5

Utilicé un árbol kd para simular el transporte de la luz a través del aerosol generado por una ola. Esto permitió obtener gotas de aerosol que no solo estaban iluminadas por lámparas, sino también luces indirectas provenientes de otras gotas. Almacenaba puntos de rocío en un árbol kd y luego usé el árbol kd para encontrar rápidamente qué puntos estaban cerca unos de otros, y de ahí qué gotas de agua se iluminaban entre sí. (En realidad, era un poco más sofisticado, pero la estructura todavía era un árbol kd). Esto hizo posible dar un agradable brillo a través del spray. Aquí hay una imagen del método en uso. No cómo el rocío alrededor de las luces brilla con luz dispersa.