Tarea 1 2020-2

En función de las consultas frecuentes que hemos identificado con respecto a la T1, hemos decidido realizar un compilado con preguntas y respuestas que les podrían servir:

¿Qué es lo que tengo que resolver?

Debes implementar un nuevo algoritmo de búsqueda, usando una BVH (se recomienda KD-Tree), tal que se reemplace el for interior por un algoritmo más eficiente. Para esto puedes añadir los archivos y structs/funciones que consideres necesarios a la carpeta src/simulate

¿Cómo calculo la mediana de los segmentos?

Esto depende de tu implementación y es parte de la tarea que determines cuál es la estrategia más efectiva. Sin embargo, las alternativas son limitadas:

1. Usar el primer punto del segmento
2. Usar el segundo punto del segmento
3. Usar el punto medio del segmento.
4. Tomar los 2 puntos de cada segmento y tomar el punto mediana de esos puntos
5. ???

¿Cómo seleccionar cuál es el segmento con el cuál dividir?

Si quieres dividir por mediana, revisa la clase de Quicksort. Si tienes otra estrategia, lo dejamos en tus manos.

¿Cómo elijo qué eje usar para dividir el espacio?

Depende de tu implementación; puedes usar un método naïve, intercalando según la altura del árbol, o un método más informado.

¿Qué hago con las cajas?

Como dijimos en el video explicativo de la T1, cada nodo del árbol tiene una caja que lo envuelve a él y por ende a toda su descendencia. Eso significa que si la partícula no choca con una caja, entonces no choca con NADA que esté bajo esa caja, ya sea otras cajas o, en las hojas, los segmentos mismos. Tú debes pensar qué hacer con esto.

¿Cómo defino una caja dado un conjunto de segmentos?

Una caja se define por dos puntos, uno mínimo y otro máximo. Un segmento es definido por dos puntos. Así, para definir la caja que envuelve un conjunto de segmentos, es necesario encontrar el punto mínimo y máximo de estos, y usarlos para definir la caja correspondiente.

Referencias y material recomendado

Videos del algoritmo de construcción de la solución de la tarea usando visualizer_draw_box. Para efectos del ejemplo, el algoritmo crea dos nuevos segmentos cuando cruza el eje divisor, así no hay traslape de cajas en un mismo nivel. Las cajas-hoja, que contienen los segmentos, se muestran en rojo.

• 8 x 8 circulos de 360 segmentos c/u Link al video
• Test 2x2 de ejemplo.
  • Elementos por hoja <= 400 Link al video
  • Elementos por hoja <= 20 Link al video
• Test 09 Link al video

Algunos videos que recomendamos revisar acerca de la construcción de un árbol de Binary Space Partitioning (que es lo que hace el KD-Tree)

Video en el que pueden observar cómo esta estructura se usa en implementaciones reales: