triangulo rectangulo pseudocodigo perimetro para cuadrado calcular algoritmo algorithm language-agnostic geometry rectangles

algorithm - rectangulo - pseudocodigo para calcular el area de un cuadrado



Algoritmo para encontrar el menor número de rectángulos para cubrir un conjunto de rectángulos sin superposición (2)

Tengo un conjunto de rectángulos y me gustaría "reducir" el conjunto, así que tengo la menor cantidad 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 la menor cantidad de rectángulos posible. Tengo un enfoque ahora que funciona la mayor parte del tiempo.

Actualmente, empiezo por el rectángulo que se encuentra más a la izquierda y veo si puedo expandirlo hacia la derecha y hacia abajo mientras lo mantengo en un rectángulo. Hago eso hasta que ya no pueda expandirme, elimine y divida todos los rectángulos que se cruzan, y vuelva a agregar el rectángulo expandido en la lista. Luego empiezo el proceso nuevamente con el siguiente rectángulo superior 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 el rectángulo amarillo (correctamente). Pero luego, cuando se procesa el resto del rectángulo amarillo, en lugar de expandirse hacia abajo, se expande hacia la derecha y recupera la parte que se había dividido previamente. Luego se procesa el último rectángulo y no se puede expandir hacia la derecha o hacia abajo, por lo que queda el conjunto original de rectángulos. Podría modificar el algoritmo para expandir primero y luego a la derecha. Eso arreglaría este caso, pero causaría el mismo problema en un escenario similar que se volteó.

Editar: solo para aclarar, el conjunto original de rectángulos no se superpone y no tiene que estar conectado. Y si un subconjunto de rectángulos está conectado, el polígono que los cubre por completo puede tener agujeros.

A pesar del título de su pregunta, creo que en realidad está buscando la mínima disección en rectángulos de un polígono rectilíneo. (Los enlaces de Jason son sobre cubiertas mínimas por rectángulos, que es un problema bastante diferente).

David Eppstein discute este problema en la sección 3 de su artículo de la encuesta de 2010 Graph-Theoretic Solutions to Computational Geometry Problems , y da un buen resumen en esta respuesta en mathoverflow.net :

La idea es encontrar el número máximo de diagonales disjuntos de eje y paralelo que tienen dos vértices cóncavos como puntos finales, dividirlos a lo largo de aquellos, y luego formar una división más para cada vértice cóncavo restante. Para encontrar el número máximo de diagonales disjuntos de eje y paralelo, forma 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 el tiempo polinomial mediante técnicas de coincidencia de gráficos.

Aquí está mi comentario sobre esta descripción admirablemente breve, 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 se encontrará con un borde de la disección. De modo que obtenemos la mínima disección si la mayor cantidad posible de estos bordes hace doble función, es decir, conectan dos de los vértices cóncavos.

Así que vamos a dibujar todas las diagonales paralelas a los ejes entre dos vértices cóncavos (una diagonal de un polígono es una línea que conecta dos vértices no adyacentes). Vamos a querer utilizar tantas de estas líneas como sea posible en la disección.

El gráfico de intersección de un conjunto de segmentos de línea tiene un nodo para cada segmento de línea, y un borde une dos nodos si las líneas se cruzan. Aquí está el gráfico de intersección para las diagonales paralelas a los ejes:

Es bipartite 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 conjunto independiente máximo en el gráfico de intersección.

Encontrar el conjunto independiente máximo en un gráfico general es un problema NP-completo, pero en el caso especial de un gráfico bipartito, el teorema de König muestra que es equivalente al problema de encontrar una coincidencia máxima, que puede resolverse en tiempo polinomial, para ejemplo por el algoritmo Hopcroft-Karp . Aquí está la coincidencia máxima:

Y aquí están la cubierta de vértice mínima correspondiente (rojo) y el conjunto independiente máximo (verde):

Traduciendo esto de vuelta al problema de disección, esto significa que podemos usar las diagonales de cinco ejes paralelos en la disección:

Finalmente, haga un corte de cada esquina cóncava restante para completar la disección: