Estou tentando cobrir um polígono côncavo simples com um mínimo de retângulos. Meus retângulos podem ter qualquer comprimento, mas têm larguras máximas e o polígono nunca terá um ângulo agudo.
Pensei em tentar decompor meu polígono côncavo em triângulos que produzem um conjunto de retângulos minimamente sobrepostos que limitam minimamente cada triângulo e depois os mesclam em retângulos maiores. No entanto, não acho que isso funcione para pequenos entalhes nas bordas do polígono. Os triângulos criados pelos vértices reflexos nesses entalhes criarão os retângulos errados. Estou procurando por retângulos que abranjam / ignorem entalhes.
Eu realmente não sei nada sobre geometria computacional, então não tenho muita certeza de como começar a fazer a pergunta.
Encontrei outros posts semelhantes, mas não o que eu preciso:
- divida o polígono em uma quantidade mínima de retângulos e triângulos
- Cobrindo um polígono arbitrário com número mínimo de quadrados
- Encontre retângulos para que cubram o número máximo de pontos
- Algoritmo para encontrar o menor número de retângulos para cobrir um conjunto de retângulos
Alguns exemplos: Preto é a entrada. Vermelho é a saída aceitável.
Outro exemplo: a segunda saída é preferida. No entanto, gerar as duas saídas e usar outro fator para determinar a preferência é provavelmente necessário e não é de responsabilidade desse algoritmo.
Polígonos que imitam curvas são extremamente raros. Nesse cenário, grande parte da área dos retângulos é desperdiçada. No entanto, isso é aceitável porque cada retângulo obedece à restrição de largura máxima.
Além disso, achei este artigo próximo ao que eu preciso:
- Cobrindo com peças retangulares de Paul Iacob, Daniela Marinescu e Cristina Luca
Talvez uma pergunta melhor seja "Como identificar partes retangulares de um polígono côncavo?"
Aqui está uma imagem mostrando a implementação desejada:
O verde é o uso real do material. Os retângulos vermelhos são os layouts. O azul é o MBR de todo o polígono. Estou pensando em tentar obter pequenos MBRs e preenchê-los. Os 2-3 retângulos verdes no canto superior esquerdo que terminam no meio do polígono são caros. É isso que eu quero minimizar. Os retângulos verdes têm largura e altura mínima e máxima, mas posso usar quantas linhas e colunas necessárias para cobrir uma região. Novamente, devo minimizar o número de retângulos que não se estendem pela entrada. Também posso modificar a forma do retângulo verde para caber em lugares pequenos que também são muito caros. Em outras palavras, obter o máximo de retângulos possível para abranger o máximo possível é ideal.
fonte
Respostas:
Esta é uma variante da capa de conjunto geométrico. Dependendo das configurações exatas, você poderá fazer uma boa aproximação. O problema é obviamente NP-Hard. Os huersíticos naturais devem usar o algoritmo guloso (sempre escolha o retângulo / faixa que cobre a maior parte da área ainda não coberta. A técnica alternativa é usar a ponderação. Existem alguns resultados teóricos interessantes, mas, francamente, nada que seja útil na prática Uma huerística interessante que você pode querer experimentar é primeiro decompor seu polígono em um número mínimo de formas convexas (usando o algoritmo de programação dinâmica Keil) e depois cobrir cada polígono convexo separadamente ...
fonte
Eu acho que este artigo pode ser de alguma ajuda. Obviamente, não é o mesmo problema - na verdade, é o problema inverso, cobrindo um retângulo com polígonos -, mas algumas das idéias podem ser um ponto de partida. Em particular, esse problema inverso é difícil para o NP e eu suspeito que o seu também pode ser (embora não haja extensão óbvia da redução, até onde eu saiba).
E. Arkin, A. Efrat, G. Hart, I. Kostitsyna, A. Kroller, J. Mitchell e V. Polishchuk. Scandinavian Thins em cima do bolo: na menor caixa de tamanho único. Diversão com algoritmos . pág.16-27. 2012
fonte