Optimal Retângulo eclosão algoritmo

Question

Eu estou procurando um algoritmo para chocar um retângulo com menor comprimento de linha, de modo que um objeto de determinada área pode ser transmitida através da incubação.

Por exemplo dado um rectângulo de 5x3 cm, e eu escotilha utilizando linhas paralelas de 1 cm de diâmetro, o maior objectivo I pode passar através da escotilha é um quadrado de lado 1 centímetro. I ter usado um total de 22 cm (ou seja, 4x3 + 2x5) de linhas de escotilha. Então, para passar uma área de 1sqcm tenho 22 centímetros usado de linhas de hachura.

O algoritmo deve encontrar um padrão que minimizar as linhas de hachura gerais de 22 centímetros atual, enquanto não permitindo que uma área com mais de 1sqcm para passar através (a necessidade objeto não ser sob a forma de um quadrado ou mesmo retângulo, que é a área total que importa).

Editar: Seguindo o exemplo de I nlucaroni encontrou o Honeycomb Conjectura , que afirma que qualquer partição do avião em regiões de igual área tem perímetro, pelo menos a da grade hexagonal regular, que responde a minha pergunta parcialmente.

Answer 1

Você precisa de formas que formam um tessellation . Hexagon é provavelmente a sua melhor aposta. Porém, o que se a forma que você está passando por não se encaixa no padrão de tessellation exatamente?

Olhe em pavimentações e descobrir se o seu padrão / tela / escotilha tem que ser regular ou não, tem que se adequar ao objeto que está sendo testado, et cetera.

Se na verdade você está construindo este de linhas retas infinitas que formam áreas = 1, então o melhor que você pode fazer é um quadrado (vá em frente, encontrar o máximo da da área no que diz respeito à relação entre os lados, ou encontrar perímetro no que diz respeito à relação de lados tomando a derivada).

sua pergunta é muito vago / incompleta, s, isso é tudo o que tenho para você.

Answer 2

problema Neat. Eu suspeito que o algoritmo vai acabar por ser muito simples, embora - deve haver algum conjunto "ótimo" de tela ângulos de usar que minimiza o tamanho da abertura para um determinado comprimento de fio

.

Na verdade, isso me lembra um pouco do problema de corte de bolo, onde você está tentando encontrar o número mínimo de cortes retos para fazer x fatias de bolo. Assim, o solutiuon pode ser ao longo das linhas, para cada fio, tente fazer a maior redução no tamanho do maior objeto que pode passar. Isso iria significar o corte das maiores "buracos" no meio com cada fio acrescentou, quando possível.

edit: Quando eu realmente tentei o meu algoritmo proposto, eu tenho resultados que eram piores do que a versão ingênua. Você definitivamente precisa ter o tamanho mínimo em consideração quando colocar os fios.

Answer 3

O que a eclodir uma média retângulo?

Você pode reformular a sua pergunta?

Além disso, durante a reformulação, estado que o algoritmo deve receber como entrada e o que deve produzir como saída.