Hispanopedia Wiki
En geometría computacional , el contenedor es una estructura de datos que permite realizar consultas de región eficientes. Cada vez que un punto de datos cae en un contenedor, la frecuencia de ese contenedor aumenta en uno. [ 1 ]
Por ejemplo, si hay algunos rectángulos alineados con los ejes en un plano 2D , la estructura puede responder a la pregunta: "Dado un rectángulo de consulta, ¿cuáles son los rectángulos que lo intersecan?" En el ejemplo de la figura superior, A, B, C, D, E y F son rectángulos existentes, por lo que la consulta con el rectángulo Q debería devolver C, D, E y F , si definimos todos los rectángulos como intervalos cerrados .
La estructura de datos divide una región del plano 2D en compartimentos de tamaño uniforme . El cuadro delimitador de cada compartimento encierra todos los rectángulos candidatos que se van a consultar. Todos los compartimentos se organizan en una matriz 2D. Todos los candidatos también se representan como matrices 2D. El tamaño de la matriz de un candidato corresponde al número de compartimentos con los que se interseca.
Por ejemplo, en la figura superior, el candidato B tiene 6 elementos dispuestos en una matriz de 3 filas por 2 columnas porque interseca 6 contenedores en dicha disposición. Cada contenedor contiene el inicio de una lista enlazada simple . Si un candidato interseca un contenedor, se enlaza a la lista enlazada de dicho contenedor. Cada elemento en la matriz de un candidato es un nodo de enlace en la lista enlazada del contenedor correspondiente.
Operaciones
Consulta
A partir del rectángulo de consulta Q , podemos determinar qué contenedor interseca eficientemente su esquina inferior izquierda restando la esquina inferior izquierda del cuadro delimitador del contenedor a la esquina inferior izquierda de Q y dividiendo el resultado por el ancho y la altura del contenedor, respectivamente. A continuación, podemos iterar sobre los contenedores que interseca Q y examinar todos los candidatos en las listas enlazadas de estos contenedores. Para cada candidato, comprobaremos si interseca Q. Si es así y no se ha informado previamente, lo informamos. Podemos usar la convención de informar un candidato solo la primera vez que lo encontramos. Esto se puede hacer fácilmente recortando el candidato con respecto al rectángulo de consulta y comparando su esquina inferior izquierda con la ubicación actual. Si hay una coincidencia, lo informamos; de lo contrario, lo omitimos.
Inserción y eliminación
La inserción es lineal con respecto al número de contenedores con los que se cruza un candidato, ya que insertar un candidato en un contenedor requiere un tiempo constante. La eliminación es más costosa porque es necesario buscar en la lista enlazada simple de cada contenedor con el que se cruza el candidato.
En un entorno multihilo, las operaciones de inserción, eliminación y consulta son mutuamente excluyentes. Sin embargo, en lugar de bloquear toda la estructura de datos, se puede bloquear un subconjunto de contenedores. Se debe realizar un análisis de rendimiento detallado para justificar la sobrecarga.
Eficiencia y ajuste
El análisis es similar al de una tabla hash . En el peor de los casos, todos los candidatos se concentran en un solo contenedor. En ese caso, la consulta es O( n ), la eliminación es O( n ) y la inserción es O(1), donde n es el número de candidatos. Si los candidatos están espaciados uniformemente de manera que cada contenedor tenga un número constante de candidatos, la consulta es O( k ), donde k es el número de contenedores que interseca el rectángulo de consulta. La inserción y la eliminación son O( m ), donde m es el número de contenedores que interseca el candidato que se inserta. En la práctica, la eliminación es mucho más lenta que la inserción.
Al igual que en una tabla hash, la eficiencia de un contenedor depende en gran medida de la distribución tanto de la ubicación como del tamaño de los candidatos y las consultas. En general, cuanto menor sea el rectángulo de consulta, más eficiente será la consulta. El tamaño del contenedor debe ser tal que contenga la menor cantidad de candidatos posible, pero lo suficientemente grande como para que los candidatos no abarquen demasiados contenedores. Si un candidato abarca muchos contenedores, una consulta debe omitirlo repetidamente después de que se reporte en el primer contenedor de intersección. Por ejemplo, en la figura, E se visita 4 veces en la consulta de Q y, por lo tanto, debe omitirse 3 veces.
Para acelerar aún más la consulta, las divisiones pueden sustituirse por desplazamientos a la derecha . Esto requiere que el número de intervalos a lo largo de una dirección del eje sea un exponente de 2.
En comparación con otras estructuras de datos de consulta de rango
Frente a un árbol k -d , la estructura de contenedores permite una inserción y eliminación eficientes sin la complejidad del reequilibrio. Esto puede ser muy útil en algoritmos que necesitan agregar formas de forma incremental a la estructura de datos de búsqueda.
Referencias
Véase también
- El árbol k -d es otra estructura de datos eficiente para consultas de rango.
- partición del espacio
- Cuantización (procesamiento de señales)
- Estructuras de datos geométricos