.net - tension - ensayo de impacto upv

Algoritmo de prueba de impacto en rectángulos que no se superponen

Question

Tengo una colección de rectángulos no superpuestos que cubren un rectángulo envolvente. ¿Cuál es la mejor manera de encontrar el rectángulo que contiene un clic del mouse?

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))?

Answer 1

Crea un árbol de intervalo. 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 que cambiar sus posiciones, por lo general.

Tendrás que tener en cuenta que, si tienes compilación, crea tus índices para diferentes ejes por separado. Por ejemplo, tienes que ver si superpones un intervalo en X y en Y. Una optimización obvia es solo verificar la superposición en cualquier intervalo X, luego verifica inmediatamente si hay superposición en Y.

Además, la mayoría de los Árboles de Intervalos de stock o de "agenda de clases" solo verifican un solo intervalo, y solo devuelven un solo Intervalo (pero dijiste "no superposición", ¿no?)

Answer 2

Puede organizar sus rectángulos en un quad o kd-tree. 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 luego está el método O (1) de simplemente generar un mapa de bits del mismo tamaño que su pantalla, llenarlo con un marcador de posición para "sin rectángulo" y dibujar los índices de hit-rectangle en ese mapa de bits. Una búsqueda se vuelve tan simple como:

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

Obviamente, ese método solo funciona bien si sus rectángulos no cambian con tanta frecuencia y si puede ahorrar memoria para el mapa de bits.

Answer 3

Tíralos en un quadtree .

Answer 4

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