Algoritmo para encontrar o menor número de retângulos para cobrir um conjunto de retângulos sem sobreposição

Eu tenho um conjunto de retângulos e gostaria de “reduzir” o conjunto para que eu tenha o menor número de retângulos para descrever a mesma área do conjunto original. Se possível, eu também gostaria que fosse rápido, mas estou mais preocupado em fazer com que o número de retângulos seja o mais baixo possível. Eu tenho uma abordagem agora que funciona na maioria das vezes.

Atualmente, começo no retângulo superior esquerdo e vejo se posso expandi-lo direito e para baixo, mantendo um retângulo. Eu faço isso até que ele não possa mais expandir, remover e dividir todos os retângulos em interseção e adicionar o retângulo expandido de volta à lista. Em seguida, inicio o processo novamente com o próximo retângulo superior esquerdo e assim por diante. Mas em alguns casos, não funciona. Por exemplo: insira a descrição da imagem aqui

Com esse conjunto de três retângulos, a solução correta terminaria com dois retângulos, como este: insira a descrição da imagem aqui

No entanto, neste caso, meu algoritmo começa processando o retângulo azul. Isso se expande para baixo e divide o retângulo amarelo (corretamente). Mas quando o restante do retângulo amarelo é processado, em vez de expandir para baixo, ele se expande primeiro e recupera a parte que foi dividida anteriormente. Então o último retângulo é processado e não pode se expandir para a direita ou para baixo, então o conjunto original de retângulos é deixado. Eu poderia ajustar o algoritmo para expandir primeiro e depois para a direita. Isso resolveria esse caso, mas causaria o mesmo problema em um cenário semelhante que foi invertido.

Edit: Só para esclarecer, o conjunto original de retângulos não se sobrepõem e não precisam ser conectados. E se um subconjunto de retângulos estiver conectado, o polígono que os cobre completamente pode ter buracos.

    Apesar do título da sua pergunta, acho que você está realmente procurando a dissecação mínima em retângulos de um polígono retilíneo. (As ligações de Jason são sobre capas mínimas por retângulos, o que é um problema bem diferente).

    David Eppstein discute este problema na seção 3 de seu artigo de pesquisa de 2010 Graph-Theoretic Solutions para Geometry Computational Problems , e ele dá um bom resumo nesta resposta em mathoverflow.net :

    A idéia é encontrar o número máximo de diagonais paralelas e paralelas que têm dois vértices côncavos como pontos finais, divididos ao longo deles, e então formar mais uma divisão para cada vértice côncavo restante. Para encontrar o número máximo de diagonais paralelas paralelas, formam o gráfico de interseção das diagonais; este grafo é bipartido, portanto, seu conjunto máximo independente pode ser encontrado em tempo polinomial por técnicas de correspondência de grafos.

    Aqui está o meu brilho nesta descrição admiravelmente concisa, usando a figura 2 do artigo de Eppstein. Suponha que tenhamos um polígono retilíneo, possivelmente com buracos.

    Quando o polígono é dissecado em retângulos, cada um dos vértices côncavos deve ser atendido por pelo menos uma borda da dissecação. Assim, obtemos a dissecação mínima, se tantas dessas bordas quanto possível fizerem o trabalho duplo, isto é, elas conectam dois dos vértices côncavos.

    Então vamos desenhar as diagonais paralelas ao eixo entre dois vértices côncavos que estão contidos inteiramente dentro do polígono. (“Eixo-paralelo” significa “horizontal ou vertical” aqui, e uma diagonal de um polígono é uma linha conectando dois vértices não adjacentes.) Queremos usar o maior número possível dessas linhas na dissecação, desde que se cruzam.

    (Se não houver diagonais paralelas ao eixo, a dissecção é trivial – basta fazer um corte de cada vértice côncavo. Ou, se não houver interseções entre as diagonais paralelas ao eixo, usamos todas elas, além de um corte de cada vértice côncavo restante Caso contrário, continue a ler.

    O gráfico de interseção de um conjunto de segmentos de linha tem um nó para cada segmento de linha e uma aresta une dois nós se as linhas se cruzarem. Aqui está o gráfico de interseção para as diagonais paralelas ao eixo:

    É bipartido com as diagonais verticais em uma parte e as diagonais horizontais na outra parte. Agora, queremos escolher o maior número possível de diagonais, desde que elas não se cruzem. Isso corresponde a encontrar o conjunto máximo independente no gráfico de interseção.

    Encontrar o conjunto independente máximo em um gráfico geral é um problema NP-difícil, mas no caso especial de um gráfico bipartido, o teorema de König mostra que é equivalente ao problema de encontrar um casamento máximo, que pode ser resolvido em tempo polinomial, exemplo pelo algoritmo Hopcroft-Karp . Um dado gráfico pode ter várias combinações máximas, mas qualquer uma delas fará, já que todas elas têm o mesmo tamanho. No exemplo, todas as correspondências máximas têm três pares de vértices, por exemplo {(2, 4), (6, 3), (7, 8)}:

    (Outras combinações máximas neste gráfico incluem {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)} e { (1, 3), (2, 4), (7, 8)}.)

    Para obter uma correspondência máxima com a cobertura de vértices mínima correspondente, aplique a prova do teorema de König . Na correspondência mostrada acima, o conjunto esquerdo é L = {1, 2, 6, 7}, o conjunto direito é R = {3, 4, 5, 8} e ​​o conjunto de vértices sem correspondência em L é U = { 1}. Existe apenas um caminho alternativo começando em U , a saber, 1–3–6, então o conjunto de vértices em caminhos alternados é Z = {1, 3, 6} e a cobertura mínima do vértice é, portanto, K = ( L \ Z ) ∪ ( RZ ) = {2, 3, 7}, mostrado em vermelho abaixo, com o conjunto independente máximo em verde:

    Traduzindo isso de volta para o problema de dissecção, isso significa que podemos usar cinco diagonais paralelas ao eixo na dissecção:

    Finalmente, faça um corte de cada vértice côncavo restante para completar a dissecação:

    Aqui estão alguns trabalhos acadêmicos discutindo soluções para este problema;

    Um Algoritmo de Aproximação Linear-Tempo para Cobertura Retangular Mínima (isto é para cobrir polígonos, então é um caso mais geral do que o que você apresentou aqui).

    Coberturas Retangulares Ótimas para Polígonos Retinolares Convexos (este é um dos mais ao longo das linhas do seu problema específico)

    Você também pode tentar aqui uma bibliografia de mais artigos sobre este assunto.