Algoritmo para la prueba de impacto en rectángulos que no se solapan

Tengo una colección de rectángulos que no se superponen que cubren un rectángulo envolvente. ¿Cuál es la mejor manera de encontrar el rectángulo que contiene un clic del mouse?Algoritmo para la prueba de impacto en rectángulos que no se solapan

La respuesta obvia es tener una matriz de rectángulos y buscarlos en secuencia, haciendo la búsqueda O (n). ¿Hay alguna forma de ordenarlos por posición para que el algoritmo sea menor que O (n), por ejemplo, O (log n) o O (sqrt (n))?

Fuente

2008-09-18 hughdbrown

Puede organizar sus rectángulos en un árbol quad o kd. Eso te da O (log n). Ese es el método principal.

Otra estructura de datos interesante para este problema son los R-trees. Estos pueden ser muy eficientes si tiene que lidiar con muchos rectángulos.

http://en.wikipedia.org/wiki/R-tree

Y después está el O (1) Método de limitarse a la generación de un mapa de bits en el mismo tamaño que la pantalla, llenarlo con un lugar titular para "no rectángulo" y sacar el hit-rectángulo índices en ese mapa de bits. Una búsqueda es tan simple como:

int id = bitmap_getpixel (mouse.x, mouse.y) 
    if (id != -1) 
    { 
    hit_rectange (id); 
    } 
    else 
    { 
    no_hit(); 
    }

Obviamente ese método sólo funciona bien si los rectángulos que no cambian con frecuencia y si se puede prescindir de la memoria para el mapa de bits.

Fuente

2008-09-18 22:51:31

El kd-tree y el R-tree son más parecidos a lo que imaginaba que era posible. La solución de mapa de bits es fuerza bruta y demostrablemente correcta, pero creo que buscaré una solución de árbol. – hughdbrown

Me gusta la idea del árbol de intervalos también. Dado que sus rectángulos no se superponen, esa puede ser la forma más sencilla de hacerlo. –

Shove them en un quadtree.

Fuente

2008-09-18 22:48:40 moonshadow

"El quadtree de región representa una partición del espacio en dos dimensiones al descomponer la región en cuatro cuadrantes iguales, subcomitantes, [...] ". ¿Qué sucede si los rectángulos no se pueden descomponer en cuadrantes iguales sino en tamaños irregulares? p.ej. 8x9 = [8x3,6x7,2x4,2x2] – hughdbrown

No solo almacene datos en las hojas, también almacene datos más arriba; almacena cada rectángulo en la rama más pequeña que lo contiene por completo. Alternativamente, almacene una referencia a cada rectángulo en cada hoja sobre la que se superpone, o utilice un [quadtree suelto] (http://tinyurl.com/3w5x27). – moonshadow

Utilice un árbol BSP para almacenar los rectángulos.

Fuente

2008-09-18 22:50:09 KPexEA

Cree un árbol de intervalos. Consulta el árbol de intervalos. Consulte 'Algoritmos' desde la prensa MIT.

Un árbol de intervalo se implementa mejor como un árbol rojo-negro.

Tenga en cuenta que solo es aconsejable ordenar sus rectángulos si va a hacer clic en ellos más seguido, por lo general, cambiará de posición.

Tendrás que tener en cuenta que, al construir, debes construir tus índices para diferentes ejes por separado. Por ejemplo, tiene que ver si superpone un intervalo en X y en Y. Una optimización obvia es solo verificar la superposición en cualquier intervalo X, luego verifique inmediatamente si hay superposición en Y.

Además, la mayoría de las existencias o 'libros de ejercicios 'Interval Trees solo verifica un solo intervalo, y solo devuelve un solo Interval (pero dijiste "no superpuesto" ¿no?)

Fuente

2008-09-18 22:56:30 Chris

Algoritmo para la prueba de impacto en rectángulos que no se solapan

Respuesta

Cuestiones relacionadas