Algoritmo para encontrar el menor número de rectángulos para cubrir un conjunto de rectángulos sin superposición
Tengo un conjunto de rectángulos y me gustaría "reducir" el conjunto para que tenga el menor número de rectángulos para describir la misma área que el conjunto original. Si es posible, me gustaría que también sea rápido, pero estoy más preocupado por conseguir el número de rectángulos lo más bajo posible. Ahora tengo un enfoque que funciona la mayor parte del tiempo.
Actualmente, comienzo en el rectángulo superior izquierdo y veo si puedo expandirlo a la derecha y hacia abajo mientras lo mantengo como un rectángulo. Lo hago hasta que ya no se puede expandir, eliminar y dividir todos los rectángulos que se cruzan, y agregar el rectángulo expandido de nuevo en la lista. Luego empiezo el proceso de nuevo con el siguiente rectángulo superior izquierdo, y así sucesivamente. Pero en algunos casos, no funciona. Por ejemplo:
Con este conjunto de tres rectángulos, la solución correcta terminaría con dos rectángulos, como este:
Sin embargo, en este caso, mi algoritmo comienza procesando el rectángulo azul. Esto se expande hacia abajo y divide la rectángulo amarillo (correctamente). Pero luego, cuando se procesa el resto del rectángulo amarillo, en lugar de expandirse hacia abajo, se expande primero a la derecha y recupera la porción que se dividió previamente. Luego se procesa el último rectángulo y no puede expandirse hacia la derecha o hacia abajo, por lo que el conjunto original de rectángulos se deja. Podría ajustar el algoritmo para expandirse primero y luego a la derecha. Eso solucionaría este caso, pero causaría el mismo problema en un escenario similar que era voltear.
Editar: Solo para aclarar, el conjunto original de rectángulos no se superponen y no tienen que estar conectados. Y si un subconjunto de rectángulos están conectados, el polígono que los cubre completamente puede tener agujeros en él.
2 answers
A pesar del título de su pregunta, creo que realmente está buscando el mínimo disección en rectángulos de un polígono rectilíneo. (Los enlaces de Jason están sobre un mínimo cubre por rectángulos, lo cual es un problema bastante diferente.)
David Eppstein discute este problema en la sección 3 de su artículo de encuesta de 2010 Soluciones gráficas Teóricas a Problemas de Geometría Computacional, y da un buen resumen en esta respuesta en mathoverflow.net :
La idea es encontrar el número máximo de ejes disjuntos: diagonales paralelas que tienen dos vértices cóncavos como extremos, dividirse a lo largo de ellos, y luego formar una división más para cada vértice cóncavo restante. Para encontrar el número máximo de diagonales paralelas-ejes disjuntos, forme el gráfico de intersección de las diagonales; este gráfico es bipartito, por lo que su conjunto independiente máximo se puede encontrar en tiempo polinómico mediante técnicas de coincidencia de gráficos.
Aquí está mi glosa en esta descripción admirablemente concisa, usando la figura 2 del artículo de Eppstein. Supongamos que tenemos un polígono rectilíneo, posiblemente con agujeros.
Cuando el polígono se diseca en rectángulos, cada uno de los vértices cóncavos debe encontrarse al menos con un borde de la disección. Así que obtenemos la disección mínima si tantos de estos bordes como sea posible hacen doble trabajo, es decir, conectan dos de los vértices cóncavos.
Así que vamos a dibujar el eje-paralelo diagonales entre dos vértices cóncavos que están contenidos enteramente dentro del polígono. ('Eje-paralelo 'significa' horizontal o vertical ' aquí, y una diagonal de un polígono es una línea que conecta dos vértices no adyacentes.) Queremos usar tantas de estas líneas como sea posible en la disección, siempre y cuando no se crucen.
(Si no hay ejes-diagonales paralelas, la disección es trivial-simplemente haga un corte de cada vértice cóncavo. O si no hay intersecciones entre el eje-diagonales paralelas a continuación, utilizamos todos ellos, además de un corte de cada vértice cóncavo restante. De lo contrario, siga leyendo.)
El gráfico de intersección de un conjunto de segmentos de línea tiene un nodo para cada segmento de línea, y una arista une dos nodos si las líneas se cruzan. Aquí está el gráfico de intersección para las diagonales paralelas del eje:
Es bipartita con las diagonales verticales en una parte, y las diagonales horizontales en la otra parte. Ahora, queremos elegir tantas diagonales como sea posible, siempre y cuando no se crucen. Esto corresponde a encontrar el máximo conjunto independiente en el gráfico de intersección.
Encontrar el máximo conjunto independiente en un grafo general es un problema NP-hard, pero en el caso especial de un grafo bipartito, el teorema de König muestra que es equivalente al problema de encontrar una coincidencia máxima, que se puede resolver en tiempo polinómico, por ejemplo, por Algoritmo de Hopcroft–Karp. Un gráfico dado puede tener varias coincidencias máximas, pero cualquiera de ellas servirá, ya que todas tienen el mismo tamaño. En el ejemplo, todas las coincidencias máximas tienen tres pares de vértices, por ejemplo {(2, 4), (6, 3), (7, 8)}:
(máximo de matchings en este gráfico se incluyen {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)}; y {(1, 3), (2, 4), (7, 8)}.)
Para obtener de un máximo coincidente el vértice mínimo correspondiente cover , aplicar la prueba del teorema de König. En el cotejo que se muestra arriba, la izquierda conjunto es L = {1, 2, 6, 7}, el conjunto de la derecha es R = {3, 4, 5, 8}, y el conjunto de inigualable vértices en L es U = {1}. Solo hay un camino alterno que comienza en U , a saber, 1-3-6, por lo que el conjunto de vértices en caminos alternos es Z = {1, 3, 6} y la cubierta mínima del vértice es así K = (L \ Z ) ∪ ( R ∩ Z) = {2, 3, 7}, se muestra en rojo a continuación, con el máximo independiente establecido en verde:
Traduciendo esto de nuevo en el problema de disección, esto significa que podemos usar cinco diagonales paralelas de eje en la disección:
Finalmente, haga un corte de cada vértice cóncavo restante para completar la disección:
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-08-09 08:02:03
Aquí hay algunos documentos académicos que discuten soluciones a este problema;
Un Algoritmo de Aproximación de Tiempo Lineal para la Cobertura Rectangular Mínima (esto es para cubrir polígonos, por lo que es un caso más general que el que ha presentado aquí).
Cubiertas rectangulares óptimas para Polígonos Rectinlineales Convexos (este es uno es más a lo largo de las líneas de su problema específico)
También puede probar aquí para una bibliografía de más documentos sobre esto tema.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-05-07 05:58:10