Algoritmo para el éxito de la prueba en la que no se solapan los rectángulos

Question

Tengo una colección de no superposición de los rectángulos que cubrir un rectángulo que encierra.¿Cuál es la mejor manera de encontrar el rectángulo que contiene un clic del ratón?

La respuesta obvia es que tienen una serie de rectángulos y a la búsqueda de ellos en secuencia, haciendo de la búsqueda de O(n).¿Hay alguna forma de ordenar por posición, de manera que el algoritmo es menor que O(n), decir, O(log n) o o(sqrt(n))?

Answer 1

Usted puede organizar su rectángulos en un quad o un kd-tree.Que te de O(log n).Que es la corriente principal método.

Otra interesante de la estructura de datos para este problema son R-trees.Estos pueden ser muy eficaces si usted tiene que lidiar con un montón de rectángulos.

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

Y luego está el O(1) método de simplemente generar un mapa de bits con el mismo tamaño de su pantalla, cubrir con un marcador de posición 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 que el método sólo funciona bien si los rectángulos no cambian a menudo, y si usted puede ahorrar la memoria para el mapa de bits.

Answer 2

Crear un Intervalo de Árbol.Consulta el Intervalo de Árbol.Consultar "Algoritmos" de MIT press.

Un Intervalo de Árbol es mejor implementado como un Árbol Rojo-Negro.

Tenga en cuenta que sólo es recomendable para ordenar su rectángulos si usted va a estar haciendo clic en ellos más que están cambiando sus posiciones, por lo general.

Deberás tener en cuenta, que han de construir construir los índices para los distintos ejes por separado.E. g., tienes que ver si se superponen un intervalo en X y en Y.Uno de los aspectos que la optimización es sólo de verificación para la superposición en cualquier intervalo X, a continuación, comprobar inmediatamente si se solapan en Y.

También, la mayoría de las acciones o 'classbook' Intervalo de Árboles de verificación sólo para un único intervalo, y devolver sólo un único Intervalo (pero usted dijo "no superpuestos", ¿no?)

Answer 3

Meter en un quadtree.

Answer 4

El uso de un BSP árbol para almacenar los rectángulos.