algorithm - Rectángulos que cubren

geometry rectangles (12)

Aquí hay un algoritmo de dividir y conquistar. AVERAGE la complejidad del caso es muy buena y diría que es algo como O(n log MaxCoords) . El peor de los casos podría ser cuadrático, sin embargo, creo que tal prueba sería bastante difícil de crear. Para hacerlo aún más difícil, haga que el orden de las funciones recursivas sea aleatorio. Tal vez lo que sugirió @Larry pueda llevar esto a O(n log n) en promedio.

No puedo encontrar una solución de línea de barrido, pero para las pruebas que he probado es muy rápido.

Básicamente, usa una función recursiva que funciona en el rectángulo azul. Primero verifique si el rectángulo azul está completamente cubierto por uno de los otros rectángulos. Si es así, hemos terminado. Si no, divídalo en 4 cuadrantes y llame recursivamente a la función en esos cuadrantes. Las 4 llamadas recursivas deben devolver verdadero. Incluyo un código C # que dibuja los rectángulos. También puede cambiarlo para que funcione con valores más grandes, pero elimine los procedimientos de dibujo en ese caso, ya que tardarán una eternidad. Lo he probado con un millón de rectángulos y un cuadrado de mil millones de lados generados de manera que no están cubiertos, y la respuesta proporcionada ( false ) tomó alrededor de un segundo en un quadcore.

He probado esto principalmente en datos aleatorios, pero parece correcto. Si resulta que no es así, simplemente eliminaré esto, pero tal vez lo ponga en el camino correcto.

public partial class Form1 : Form { public Form1() { InitializeComponent(); } List<Rectangle> Rects = new List<Rectangle>(); private const int maxRects = 20; private void InitRects() { Random rand = new Random(); for (int i = 0; i < maxRects; ++i) // Rects[0] is the model { int x = rand.Next(panel1.Width); int y = rand.Next(panel1.Height); Rects.Add(new Rectangle(new Point(x, y), new Size(rand.Next(panel1.Width - x), rand.Next(panel1.Height - y)))); } } private void DrawRects(Graphics g) { g.DrawRectangle(Pens.Blue, Rects[0]); for (int i = 1; i < Rects.Count; ++i) { g.DrawRectangle(Pens.Red, Rects[i]); } } private bool Solve(Rectangle R) { // if there is a rectangle containing R for (int i = 1; i < Rects.Count; ++i) { if (Rects[i].Contains(R)) { return true; } } if (R.Width <= 3 && R.Height <= 3) { return false; } Rectangle UpperLeft = new Rectangle(new Point(R.X, R.Y), new Size(R.Width / 2, R.Height / 2)); Rectangle UpperRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y), new Size(R.Width / 2, R.Height / 2)); Rectangle LowerLeft = new Rectangle(new Point(R.X, R.Y + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2)); Rectangle LowerRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y + + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2)); return Solve(UpperLeft) && Solve(UpperRight) && Solve(LowerLeft) && Solve(LowerRight); } private void Go_Click(object sender, EventArgs e) { Graphics g = panel1.CreateGraphics(); panel1.Hide(); panel1.Show(); Rects.Clear(); InitRects(); DrawRects(g); textBox1.Text = Solve(Rects[0]).ToString(); }

Tengo N rectángulos con lados paralelos a los ejes x e y. Hay otro rectángulo, modelo . Necesito crear un algoritmo que pueda indicar si el modelo está completamente cubierto por los rectángulos N.

Tengo algunas ideas. Creo que primero, debo ordenar los rectángulos por su lado izquierdo (se puede hacer en tiempo O (n log n) ), y luego usar una línea de barrido vertical.

+------------------------------------------------------------> x |O | +----+ | +---------+ | | | | ++----+--+ | | | +-++----+-+| | | | | | +-++-+ | +------+ +-------++ | +---------+ | | | |y

El rectángulo azul es el modelo .

En primer lugar, necesito el algoritmo abstracto. No hay requisitos especiales con respecto a la realización. Un rectángulo se puede representar como un par de puntos (izquierda-arriba y abajo-derecha).

Esta es una de las tareas para prepararse para una prueba. Sé que el mejor algoritmo puede hacer esto en tiempo O (n log n) .

Aquí hay un algoritmo genérico

¿Hay algún rectángulo que cubra todo el modelo?
si sí, has terminado
Si no hay rectángulos que cubren parcialmente el modelo?
en caso afirmativo
es la unión de todas las intersecciones de rectángulo y modelo igual al modelo
si 2. o 3. es no, entonces la respuesta es no, de lo contrario es sí

Ahora la pregunta es cómo hacer lo anterior de manera eficiente. Lo anterior se puede hacer en un solo bucle sobre todos los polígonos, así que creo que está mirando el tiempo O (n).

Si necesita crear un algoritmo eficiente que pruebe múltiples modelos, o si debe optimizar para obtener la respuesta más rápida posible (a costa de preparar los datos), entonces está buscando una estructura que le permita responder rápidamente si un rectángulo se interseca ( o contiene) un rectángulo.

Si usa, por ejemplo, kd-trees , creo que esto se puede responder en tiempo O (log n), pero la variable importante en este algoritmo también es el número de rectángulos encontrados k. Terminará con algo como O (k + log n) y también necesitará hacer la parte de la unión para probar si el modelo está cubierto.

Mi conjetura es que la unión podría calcularse en O (k log k), por lo que si k es pequeña, entonces está mirando O (log n) y si k es comparable a n, entonces debería ser O (k log k).

Véase también this pregunta.

EDITAR: En respuesta a la complejidad de las intersecciones y uniones.

En más detalles, tenemos dos escenarios dependiendo de si k << n o k es comparable a n

a) en el caso de k << n y suponiendo una complejidad polinomial para la intersección / unión (de modo que aquí renuncio a la conjetura O (k log k)) tenemos:

log n para encontrar un rango en kd árbol indexado (de rectángulos),
k pasos para recuperar todos los rectángulos en esa ''rama'',
f (k) algún tiempo polinomial para calcular intersecciones y unión

El total es O (k + log n + f (k)), que es directamente igual a O (log n), ya que O grande depende solo del término de más rápido crecimiento.

En este caso, la parte más significativa del algoritmo es encontrar los polígonos.

b) en el caso de k comparable a n, debemos analizar la complejidad de los algoritmos de intersección y unión (observe el paralelo aquí sobre cómo las RDBM, según la selectividad, pueden usar el índice o la exploración de tablas; es una opción similar a lo que tenemos aqui).
Si k es lo suficientemente grande, el algoritmo se vuelve menos que un algoritmo para encontrar rectángulos que se intersecan con el rectángulo y se convierte más en un algoritmo para calcular la unión de polígonos.

Pero, creo que el árbol kd también puede ayudar a encontrar la intersección de segmentos (que son necesarios para construir la unión), por lo que incluso esta parte del algoritmo podría no necesitar k ^ 2 tiempo. En este punto, investigaría algoritmos eficientes para calcular el área de uniones.

Aquí hay una manera de hacer esto sin usar rasterización, es decir, usando solo números puros.

Nota : Esto no es O (n log n), más como O (n ^ 2). Es, sin embargo, una solución. Si es una respuesta, probablemente no si O (n log n) es un requisito.

Cree una lista de todas las coordenadas X únicas de los bordes izquierdo y derecho (en la misma lista)
Cuando construya esta lista, para cada coordenada, también asocie una lista de rectángulos con ella, e indique en esta lista si la coordenada X a la que está asociada la lista es el borde izquierdo o derecho del rectángulo.
Ordena la lista de coordenadas para que sea ascendente, yendo de izquierda a derecha.
Crear una nueva lista de rectángulos, inicialmente vacía
Recorra la lista de coordenadas y procese la lista de rectángulos asociada.
Todos los rectángulos en la lista asociada que se denotan que tienen la coordenada como el borde izquierdo deben agregarse a la lista que creó en 4.
Deben eliminarse todos los rectángulos con la coordenada como el borde derecho.
El orden de adición y eliminación debe realizarse en el orden opuesto, primero desea eliminar los rectángulos del borde derecho y luego agregar todos los rectángulos del borde izquierdo
Ahora, antes de eliminar los rectángulos de la lista que creó en 4, desea procesarlos. Los procesa tratándolos como "sub-rectángulos". Su "nueva" coordenada del borde izquierdo es la coordenada X que usted procesó en la iteración anterior del bucle (en 5), y el nuevo borde derecho es la coordenada X actual que se está procesando
La salida del algoritmo es una colección de pares de coordenadas (las dos coordenadas X izquierda y derecha), cada par tiene una lista de rectángulos asociada (la franja vertical)

Por lo tanto, la salida debería ser:

X = 1..2, rectas = A
X = 2..3, rectas = A, B
X = 3..4, rectas = A, B, C
X = 4..5, rectas = A, C
X = 5..6, Rects = C

Déjame ilustrar el proceso hasta ahora

+-------------------+ |A | | +----------+-----+ | |C | | | +-----+----+ | | | |B | | | | | | +----+-----+-----+ | | | | +--+----------+-----+ | | +----------+ ^ ^ ^ ^ ^ ^ 1 2 3 4 5 6 <-- X-coordinates

Rectángulos asociados:

izquierda: A, derecha: (ninguna)
izquierda: B, derecha: (ninguna)
izquierda: C, derecha: (ninguna)
izquierda: (ninguna), derecha: B
izquierda: (ninguna), derecha: A
izquierda: (ninguna), derecha: C

Ahora crea una lista vacía, L=[] , y comienza a procesar las coordenadas y los rectángulos asociados:

X = 1

La lista está vacía, no hay nada que procesar. Nada que quitar. Agregar A: L = [A]

X = 2

La lista contiene rectángulos, la lista de procesos como rectángulos que tienen un borde izquierdo de X = 1, y un borde derecho de X = 2 (las dos coordenadas que hemos procesado hasta ahora), y usan sus coordenadas superiores e inferiores originales. Nada que quitar. Añadir B: L = [A, B]

X = 3

La lista contiene rectángulos, la lista de procesos (tanto A como B) de la misma manera, trátelos como si tuvieran temporalmente coordenadas izquierda y derecha como X = 2 y X = 3, y use sus coordenadas superiores e inferiores originales. No hay nada que eliminar. Añadir C: L = [A, B, C]

X = 4

Procese los tres rectángulos de la misma manera que arriba, las coordenadas temporales izquierda y derecha son X = 3 y X = 4 Eliminar B: L = [A, C] No hay nada que agregar

X = 5 y X = 6

Procésalos de la misma manera.

Esto significa que terminará con "tiras" de rectángulos, como esto (las he separado un poco para aclarar que son tiras, pero están ubicadas una al lado de la otra continuamente como en el diagrama original):

+--+ +-----+ +----+ ------+ |A | | | | | | | | | | | +----+ +-----+ +-----+ | | | | |C | | | | | | | +-----| +----+ | | | | | | |B | | | | | | | | | | | +----+ +-----| +-----+ | | | | | | | | +--+ +-----+ +----+ +-----+ | | | | +-----+ +----+ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 1 2 2 3 3 4 4 5 5 6

Bien, ahora tienes tu salida, una colección de pares de coordenadas, cada par tiene una lista de rectángulos asociada.

Ahora hacemos un truco. Procesamos la franja vertical de la misma manera, solo que esta vez usamos las coordenadas Y como delimitadores. Manejemos la tira entre 3 y 4 arriba. Recuerda que la tira tiene unas coordenadas de izquierda y derecha de 3 y 4.

Strip se ve así:

^ +----+ <-- 1 A | | | ^ +----+ <-- 2 | C | | | ^ | +----+ <-- 3 | B | | | | | V +----+ <-- 4 | | | | V | +----+ <-- 5 | | | V +----+ <-- 6

Lista de coordenadas con rectángulos:

Top = A, Bottom = (ninguno)
Top = C, Bottom = (ninguno)
Arriba = B, Abajo = (ninguno)
Superior = (ninguno), Inferior = C
Arriba = (ninguno), Abajo = A
Top = (ninguno), Bottom = B

Nueva lista vacía L = []

Procesar las coordenadas:

Y = 1

Nada para procesar (L = []) Agregar A a la lista, L = [A]

Y = 2

El proceso A tiene temporalmente coordenadas superior e inferior de Y = 1 y 2 (y recuerde que también tiene coordenadas temporales de izquierda y derecha de X = 3 y 4 Agregue C, L = [A, C]

Y = 3

Proceso A y C, ambos ahora tienen coordenadas temporales de (3, 2) - (4, 3) Agregue B, L = [A, B, C]

Y = 4

Proceso A, B y C, todos con coordenadas de (3, 3) - (4, 4) Eliminar C, L = [A, B]

Y = 5

Proceso A y B, coordenadas (3, 4) - (4, 5) Eliminar A, L = [B]

Y = 6

Proceso B, coordenadas (3, 5) - (4, 6)

Salida final:

pares de coordenadas Y, con rectángulos asociados (que también tienen nuevas coordenadas X):

(3, 1) - (4, 2) - A
(3, 2) - (4, 3) - A, C
(3, 3) - (4, 4) - A, B, C
(3, 4) - (4, 5) - A, B
(3, 5) - (4, 6) - B

Ahora, suponga que quiere hacer la pregunta: ¿Está B completamente cubierta por cualquier combinación de los otros rectángulos?

La respuesta se puede resolver de la siguiente manera:

Recorre todos los rectángulos en la lista final de arriba
Si B NO es parte del rectángulo asociado, ignore este rectángulo
Si hay algún otro de los rectángulos originales asociados con las coordenadas, entonces esta parte de B está cubierta por ese / esos rectángulo (s)
Si no hay otro de los rectángulos originales asociados con las coordenadas, entonces esta parte de B no está cubierta.

En el ejemplo anterior, vemos que los rectángulos tercero y cuarto en la lista final contienen B, pero también contiene otros rectángulos, por lo tanto, esas partes de B están cubiertas, pero el rectángulo final en la lista también contiene B, pero ningún otro rectángulo, por lo tanto esta parte no está cubierta.

De acuerdo con el diagrama original, el resultado final incluiría los rectángulos de la siguiente manera (las letras dentro de cada uno indican qué rectángulo original está asociado con este nuevo rectángulo):

+--+-----+----+-----+ |A |A |A |A | | | +----+-----+-----+ | | |AC |AC |C | | +-----+----+ | | | |AB |ABC | | | | | +----+-----+-----+ | | |AB |A | +--+-----+----+-----+ |B |B | +-----+----+

Si ahora echamos un nuevo vistazo al diagrama original, he sombreado las partes que el algoritmo anterior encontraría que contiene B, pero ningún otro rectángulo:

+-------------------+ |A | | +----------+-----+ | |C | | | +-----+----+ | | | |B | | | | | | +----+-----+-----+ | | | | +--+-----+----+-----+ |#####|####| +-----+----+

La barra vertical en el centro es para ilustrar que la parte se devolvería como dos rectángulos, divididos en esa ubicación, debido a la forma en que se trabajaron las tiras verticales.

Espero seriamente haberme hecho entender aquí. Tengo un código que puede ayudarlo con la implementación de cada corrida a través de las listas de coordenadas, pero son las 01:21 pasadas la medianoche y me voy a dormir, pero deje un comentario si desea ver un código real para esto .

O sería un gran ejercicio implementarlo usted mismo :)

Aquí está el enlace a la clase que contiene el método en cuestión: RangeExtensions.cs .

El método es el Slicemétodo, solo busca en la página. El tipo en cuestión, Rango, es básicamente un rango de un valor a otro, por lo que hay un poco de construcción y mantenimiento de datos además del algoritmo anterior.

Bien, ahora parece que ni siquiera puedo dormir por la noche porque pienso en este problema ... pero también parece que finalmente obtuve una solución O (n log n) , en un caso promedio (pero con pocas posibilidades de tener una enfermedad patológica). entrada en comparación con @lVlad ).

Todos conocemos la técnica Dividir y Conquistar . Para garantizar que O(n log n) use, usualmente nos enfocamos en 2 puntos:

la división y la fusión deben ser O(n)
existe C> 1 tal que en cada paso el tamaño de los subproblemas se reduce en un factor C (constante a lo largo del problema)

Teniendo en cuenta estas limitaciones, he elaborado el siguiente algoritmo, que recuerda a qsort , y por lo tanto sufre los mismos inconvenientes (es decir, entradas fractales).

Algoritmo

Recorte : solo consideramos la parte de un red que se interseca con el blue , se insertan en un HashSet para eliminar duplicados -> O(n)
Selección de pivote : más sobre esto más adelante -> O(n)
Partición : una vez que tenemos un pivote, subdividimos el espacio en 3 zonas ^d , una de las cuales es el pivote, siendo d la dimensión (d = 1 para segmentos, 2 para rectángulos, 3 para cubos, etc.)
Reparto : colocamos el red en las particiones, aplicando la técnica de recorte, observamos que un red dado podría terminar dando varios fragmentos en diferentes particiones
Recursión : aplicamos recursivamente (desde el paso 2) en cada partición, comenzando por la menos poblada y parando tan pronto como no se cubre una.

La elección de pivote es la piedra angular del algoritmo, si la partición no está bien diseñada no podemos lograr la complejidad requerida. Además, debe cumplirse en O(n) . Tengo 2 propuestas hasta ahora:

Maximum Area : use el rectángulo con el área más grande, porque significa que las particiones tendrán el área más pequeña después, sin embargo, no es fácil de vencer
Median of 3 : basada en qsort, selecciona 3 elementos, selecciona la mediana (la que tiene el centro más cerca del centro de los 3 centros)

Propongo mezclarlos así:

Recoge los 3 elementos con el área más grande, selecciona la mediana, úsala en el pivote
Si después de la partición resulta que una de las particiones está poblada con más de N / C (para personalizar), elija 3 elementos al azar, seleccione la mediana y haga la partición (no haga clic aquí)

Otro aspecto de la implementación es la cola de la recursión. Como qsort , es probable que el algoritmo sea ineficiente para n pequeña. En lugar de llegar a 1, propongo usar el truco introsort : si n es más pequeño que, por ejemplo, 12, entonces use el siguiente algoritmo:

Para cada eje, proyecte cada red en el eje (solo los bordes) y ordénelos (ala introsort)
Esto define un ráster de zonas nd, compruebe que cada uno está cubierto

Dimensión agnóstica

El algoritmo se define formalmente para ser aplicable en cualquier dimensión dada con la misma complejidad asintótica, en promedio O (n log n) . Esto nos da la oportunidad de probar en la dimensión 1 para identificar las entradas patológicas.

Entrada patológica

Al igual que qsort en el que se modela, es sensible a las entradas factoriales. Por entradas factoriales quiero decir:

1.......6...9.11.13

siempre que elija el promedio de su intervalo, tendrá todos los elementos en un lado.

Con tal entrada, incluso la elección de la mediana de 3 es poco probable que produzca un buen corte.

EDITAR:

Voy a mostrar la idea de la partición con un pequeño esquema, ya que @lVlad señaló que era un poco confuso.

+----------------+----+---------+ | 1 | 2 | 3 | +----------------+----+---------+ | 8 | P | 4 | +----------------+----+---------+ | 7 | 6 | 5 | +----------------+----+---------+

Bien, entonces el rectángulo que verificamos para la cobertura ahora está dividido en 9 subrectangles. Ignoramos P, es nuestro pivote.

Ahora, realmente nos gustaría que cada subrectangle esté cubierto por menos red que N El pivote se elige como un centro de concentración de los centros, por lo que significa que si nuestra elección "aleatoria" es cierta, existen aproximadamente tantos centros red en cada dirección del pivote.

Es un poco confuso allí porque algunas configuraciones especiales pueden hacer que haya poca ganancia en un paso (todos los rectángulos tienen el mismo centro y solo seleccionamos el más pequeño, por ejemplo), pero creará un caos y, por lo tanto, el siguiente paso sé diferente.

Estoy feliz si alguien puede formalizar eso, soy un ingeniero, no un científico informático, y mis matemáticas se quedan atrás ...

Es difícil saber lo que está buscando, pero me parece que un R-tree podría funcionar.

Estás en el camino correcto con la línea de barrido. Conceptualmente, queremos detectar cuándo la intersección del modelo con la línea de barrido no está cubierta por los otros rectángulos. La plantilla de alto nivel consiste en dividir cada rectángulo en un "borde izquierdo" y un evento del "borde derecho", ordenar los eventos por la coordenada x (colocar las izquierdas antes de los derechos si los rectángulos están cerrados y los derechos antes de las izquierdas si están abiertos), y luego procesar cada evento en tiempo O (log n). Esto es básicamente tarea, así que no diré más.

Hay un enfoque trivial O(N^2) que es similar al enfoque "raster" que se muestra. Como todos los rectángulos son paralelos al eje, solo puede haber como máximo 2N distintas dimensiones x e y. Ordene todas las x y las y, y reasigne: x_i -> i . Así que ahora tienes una matriz 2N x 2N donde puedes usar fácilmente el algoritmo ingenuo O(N^2) .

Lo he estado pensando y creo que finalmente entendí lo que @algorithmist quería decir con línea de barrido . Sin embargo, la presencia misma de las operaciones de sorting significa que tengo:

O(n log n) en promedio
O(n**2) en el peor de los casos.

Línea de barrido

En primer lugar, necesitamos un poco de clasificación, porque nuestra sweep line consistirá en caminar un juego ordenado.

Este conjunto ordenado contará con la línea top e bottom de cada uno de los red , siempre que se encuentren entre la top e bottom del blue . Esto divide nuestro espacio en (a lo sumo) n*2 tiras horizontales.

Ahora, debemos asegurarnos de que en cada strip , todo el blue esté cubierto, y esta operación no puede tener más de O(log n) complejidad, esto podría hacerse si tuviéramos (para cada tira) una lista de los cubiertos. intervalos Este es el ''evento'' que habla @algorithmist

Para manejar este evento, usaremos un árbol binario que se describe a continuación, que se encarga de agregar o eliminar un rectángulo en exactamente las operaciones O(log n) y produce el intervalo más a la derecha cubierto por el árbol, que usamos para indicar si la franja de blue es Cubierto o no.

Árbol binario

En primer lugar, voy a indexar los rectángulos red . Los ordenamos usando esta función:

def __lt__(lhs, rhs): return (lhs.left < rhs.left) or (lhs.left == rhs.left and lhs.right < rhs.right)

Entonces voy a crear un árbol binario dedicado.

Tendrá N hojas, cada una representando un rectángulo red e indicando su presencia o ausencia. Se ordenan según el índice.
Cada nodo intermediario tendrá por valor el intervalo más a la derecha cubierto por sus hijos

Manejo del error "bloque de código no puede seguir la lista":

class Node: def __init__(self): self.interval = [] self.left = None self.right = None

Ahora tenemos dos posibilidades, digamos que los niños cubren [a,b] y [c,d] :

si c <= b , entonces el nodo mantiene [a,d]
de lo contrario tiene [c,d]

¿Por qué funciona? Tomemos un ejemplo usando 4 hojas:

_ [1,9] _ / / [1,7] [6,9] <-- Special node merge / / / / / / / / [1,3] [2,7] [3,5] [6,9]

El nodo especial se ignora [3,5] porque no es el intervalo más a la derecha. El razonamiento es que los rectángulos están ordenados:

Ningún rectángulo a la derecha de [6,9] cubrirá el intervalo [5,6] faltante, ya que comienzan después de 6
Los rectángulos a la izquierda de [3,5] comienzan antes de 3 , por lo que si cubren lo que falta [5,6] , cubrirán [3,5] todos modos

La raíz puede no indicar el conjunto exacto de intervalos cubiertos: solo el intervalo más a la derecha cubierto. Sin embargo, ¡es perfectamente suficiente para nosotros saber si el blue está completamente cubierto o no!

Hay 2 operaciones disponibles en este árbol:

Marcando un rectángulo como presente
Marcar un rectángulo como ausente

Cada uno es similar:

Si el rectángulo ya estaba en este estado, no haga nada.
de lo contrario, alterne su estado, luego actualice su intervalo padre (recursivamente, hasta la raíz)

El bit recursivo toma O(log n) . Es una propiedad clásica de los árboles binarios equilibrados. Y una vez hecho esto, tenemos el intervalo más a la derecha cubierto por la raíz, que es suficiente para saber si el segmento blue está cubierto por completo o no.

Complejidad

La complejidad del algoritmo es simple:

Tenemos O(n) eventos
Cada evento se maneja en O(log n)

Lo que produce O(n log n) para la parte central.

Sin embargo, no debemos olvidar que también tenemos 2 operaciones de sort :

Uno para clasificar los eventos (para la línea de barrido).
el otro para clasificar los rectángulos (para el árbol binario)

Cada uno tomará O(n log n) en promedio , pero puede degenerar en O(n**2) en el peor de los casos, dependiendo del algoritmo de clasificación utilizado.

OK, he hecho suficientes preguntas, aquí hay una respuesta ...

Si los datos se representan como un algoritmo ráster, es trivial:

Cree una matriz booleana que represente el rectángulo del modelo (es decir, el azul). Establezca todos los elementos en FALSO (que representa ''no cubierto'')
Para cada rectángulo rojo (ignore los que no pueden solaparse con el azul), configure todos los elementos de la matriz en VERDADERO si están dentro del rectángulo rojo.
Finalmente, verifique si todos los elementos de la matriz se han establecido como VERDADEROS.

Si los datos son vectoriales es un poco más complicado. Primero defina una función que devuelva el rectángulo que representa la intersección (si existe) de dos rectángulos. Esto es simple. Luego proceda:

Cree una variable llamada ''UnCoveredRectangle'' que se inicializa para que sea la misma que el rectángulo azul.
Nuevamente, solo molesta con los rectángulos rojos que intersectan el azul. Para cada rectángulo rojo, calcula la intersección del rectángulo con UnCoveredRectangle. La intersección dará lugar a una de las siguientes situaciones:
2.1 La intersección es igual a UnCoveredRectangle. El trabajo está terminado.
2.2 La intersección ''muerde'' un trozo rectangular fuera del CoveredRectangle. El UnCoveredRectangle restante será un rectángulo, una pieza en forma de L o una pieza en forma de U. Si es un rectángulo en sí mismo, configure UnCoveredRectangle para que sea el rectángulo restante, y vaya al paso 2. Si el UnCoveredRectangle tiene forma de L o U, divídalo en 2, o 3, rectángulos y retroceda desde el paso 2 ..
Si se queda sin rectángulos rojos antes de que el área de (parte de) UnCoveredRectangle se envíe a 0, ha finalizado.

OK, no tengo ni idea de la complejidad de este algoritmo, pero a menos que la cantidad de rectángulos sea enorme, no me preocupa demasiado, aunque tal vez lo sea @den. Y he omitido muchos detalles. Y no puedo dibujar bonitos diagramas como lo hizo @den, así que tendrán que imaginárselo a ustedes mismos.

Aquí hay un enfoque de tiempo de ejecución O (n lg n) usando algo de memoria.

Usando el ejemplo:

Solo nos interesa la parte parcial de la escena que contiene el rectángulo ''modelo''; en este ejemplo, el rectángulo ''modelo'' es1,1 -> 6,6

1 2 3 4 5 6 1 +---+---+ | | 2 + A +---+---+ | | B | 3 + + +---+---+ | | | | | 4 +---+---+---+---+ + | | 5 + C + | | 6 +---+---+

1) recopile todas las coordenadas x que están dentro de los límites del rectángulo del modelo (tanto a la izquierda como a la derecha) en una lista, luego ordénelo y elimine los duplicados

1 3 4 5 6

2) recopile todas las coordenadas y que están dentro de los límites del rectángulo del modelo (arriba y abajo) en una lista, luego ordénelo y elimine los duplicados

1 2 3 4 6

3) cree una matriz 2D por número de espacios entre las coordenadas x únicas * número de espacios entre las coordenadas y únicas. Esto puede usar un solo bit por celda, y puede considerar usar el bit_vector () de C ++ STL para una representación eficiente.

4 * 4

4) pinte todos los rectángulos en esta cuadrícula, pintando la celda sobre la que ocurre:

1 3 4 5 6 1 +---+ | 1 | 0 0 0 2 +---+---+---+ | 1 | 1 | 1 | 0 3 +---+---+---+---+ | 1 | 1 | 2 | 1 | 4 +---+---+---+---+ 0 0 | 1 | 1 | 6 +---+---+

5) Si alguna celda permanece sin pintar, sabrá que su modelo no está completamente ocluido (o lo que esté probando).

Las coordenadas de recolección y los pasos de pintura son O (n), y la clasificación de las coordenadas es O (n lg n).

Esto se adaptó de una de mis respuestas a: ¿Qué es un algoritmo eficiente para encontrar el área de rectángulos superpuestos?

¿Conoce el O(nlogn)algoritmo de peor caso habitual para el área de la unión de rectángulos ?

Todo lo que necesitas hacer aquí es calcular las dos áreas:

El área de tus rectángulos N
El área de tus N rectángulos y el modelo.

Si estas áreas son iguales, el modelo está totalmente cubierto, de lo contrario no lo es.

Aquí se explica cómo hacer que un sweepline funcione en O (n lg n). Me centraré en la parte difícil de cómo funciona el BST.

Mantenga una BST balanceada que contenga el inicio y el final de cada rectángulo que se interseca con el sweepline actual. Cada nodo de la BST contiene dos campos auxiliares: minOverlap y deltaOverlap. El campo minOverlap generalmente almacena el número mínimo de rectángulos que se superponen a cualquier punto en el intervalo cubierto por el subárbol de ese nodo. Sin embargo, para algunos nodos el valor está ligeramente desactivado. Mantenemos un invariante que minOverlap más la suma de deltaOverlap para cada nodo hasta la raíz tiene el número mínimo verdadero de rectángulos que se superponen a una región en el subárbol del nodo.

Cuando insertamos un nodo de inicio de rectángulo, siempre insertamos en una hoja (y posiblemente rebalanceamos). A medida que avanzamos por la ruta de inserción, "empujamos hacia abajo" cualquier valor deltaOverlap distinto de cero a los elementos secundarios de la ruta de acceso del nodo insertado, actualizando el minOverlap de los nodos en la ruta de acceso. Luego, necesitamos incrementar cada nodo a la ''derecha'' del nodo insertado en el árbol en tiempo O (lg n). Esto se logra incrementando el campo minOverlap de todos los ancestros correctos del nodo insertado e incrementando el deltaOverlap de todos los hijos correctos de los ancestros correctos del nodo insertado. Se realiza un proceso análogo para la inserción del nodo que finaliza el rectángulo, así como la eliminación de puntos.Se puede realizar una operación de reequilibrio modificando solo los campos de los nodos involucrados en la rotación. Todo lo que tiene que hacer es verificar la raíz en cada punto del barrido para ver si el mínimo de superposición es 0.

He omitido detalles sobre cómo manejar cosas como las coordenadas duplicadas (una solución simple es ordenar los nodos de rectángulo abierto antes que los nodos de rectángulo cerrado de la misma coordenada), pero espero que le dé la idea y sea razonablemente convincente.