Como criar um algoritmo para organizar janelas (redimensionáveis) na tela para cobrir o máximo de espaço possível?

20

Eu gostaria de escrever um programa simples que aceite um conjunto de janelas (largura + altura) e a resolução da tela e produza um arranjo dessas janelas na tela, para que as janelas ocupem mais espaço. Portanto, é possível redimensionar uma janela, mantendo output size >= initial sizee a proporção. Então, para a janela , eu gostaria que o algoritmo retornasse uma tupla .( x , y , w i d t h , h e i g h t )Eu(x,y,width,height)

Eu acredito que isso pode ser uma variação da mochila 2D. Eu tentei revisar os resultados na Web, mas eles tinham muitos antecedentes (e nenhuma implementação) que dificultavam o meu acompanhamento.

Estou menos interessado no algoritmo mais rápido possível, mas mais em algo que seja prático para minha necessidade específica.

daniel.jackson
fonte
1
Se você está redimensionando uma janela, não está "mantendo seu tamanho inicial", apenas sua proporção, presumo.
Emre
1
Você pode redimensionar uma janela para cobrir a tela, qual é o problema?
2
Eu segundo o comentário de Saeed. Você precisa de restrições adicionais, como tamanhos mínimos, com o objetivo de minimizar a soma dos redimensionamentos, se desejar excluir soluções triviais. Nota bene: matemáticos parecem chamar ladrilhos problemas pavimentações .
Raphael
1
Talvez seja melhor dizer, você deseja maximizar a área mínima da janela visível e minimizar a área máxima da janela visível, mas conflitos são permitidos ou não? Edite sua pergunta para torná-la livre de erros, não é fácil pensar na declaração do problema atual.
2
WminWWsEuze(W)W

Respostas:

9

Embora sua pergunta não diga isso, estou assumindo que você não deseja que as janelas se sobreponham.

Uma abordagem para esse problema é usar um solucionador de restrições como o Choco . Basta escrever as restrições que codificam o seu problema, ajustar o solucionador para agir de maneira inteligente e depois deixá-lo funcionar. Isso significa que todo o pensamento que você precisa fazer será gasto em encontrar uma boa maneira de codificar o problema, não em criar um algoritmo e fazer a programação e o ajuste. Aqui está uma resposta parcial para você começar.

Suponha que o tamanho da tela seja .xmumax×ymumax

Para cada janela, , você terá um conjunto de variáveis e restriçõesx i , y i , h i , w iWEuxEu,yEu,hEu,WEu

  • xEu,yEu,hEu,WEu0 0
  • xEu+WEuxmumax
  • yEu+hEuymumax
  • Talvez também algumas restrições quanto ao tamanho mínimo das janelas, por exemplo, e assim por diante.hEu100
  • Restrições aspecto: Se proporção é de 3: 4, a restrição poderia ser algo como , onde ε é um pequeno termo de erro diferente de zero para permitir a janela não-perfeito tamanhos, caso contrário você restringiria demais o problema.4hEu-ϵ3WEu4hEu+ϵϵ

Agora você precisa cuidar da sobreposição da janela. Para cada par de janelas, , onde i j , você vai gerar constrangimentos como o seguinte, que capturam que nenhum canto do W j aparece dentro W i . Para ( x , y ) { ( x j , y j ) , ( x j + w j , y j ) , ( x j , yWEu,WjEujWjWEu , gera restrição:(x,y){(xj,yj),(xj+Wj,yj),(xj,yj+hj),(xj+Wj,yj+hj)}

  • .¬(xEuxxEu+WjyEuyyEu+hj)

As restrições especificadas até agora descrevem apenas janelas não sobrepostas que não se espalham pelas laterais da tela, que atendem a algumas restrições de tamanho mínimo e que preservam sua proporção.

Para obter um bom ajuste, é necessário especificar uma métrica que capture o que significa ser um bom layout. Uma possibilidade é supor que você deseja manter as janelas aproximadamente iguais em tamanho e / ou que deseja minimizar o "espaço em branco". Eu não acho que isso possa ser especificado usando o Choco, mas pode ser possível com outra solução de restrição (alguém pode ajudar aqui).

Choco permite maximizar o wrt para uma função objetiva especificada como uma única variável. Com base nessa idéia, você pode maximizar o seguinte:

  • Eu(hEu+WEu)

escrevendo uma restrição e dizendo ao Choco para maximizar c o s t .cost=Eu(hEu+WEu)cost

Dave Clarke
fonte
Isso parece promissor e definitivamente vou brincar com o Choco para ver como isso funciona e com que rapidez.
Daniel.jackson 12/04/12
Mas por que dizer isso de maneira geral? Eu acho que você pode descrever as restrições como desigualdades lineares, o que significa que o que você tem é um programa linear de baunilha.
Suresh
@ Suresh: Sinta-se livre para elaborar. Eu não vejo imediatamente como.
Dave Clarke
1

Comecei a escrever um protótipo para uma solução de força bruta, que espero possa ser otimizada até um ponto em que seja prático.

Primeiro, algumas definições: Seja o conjunto de todas as janelas. Cada janela w é composta por x w , y w , w w , h w para as coordenadas x, y e a largura e altura. Uma janela é inicializada com largura e altura mínimas.WWxW,yW,WW,hW

A entrada do algoritmo é a tela , que possui largura e altura e uma lista de janelas.S

Funciona aproximadamente assim:

void fit(W, S, i, n, result)
    if i == n
        if S.score() < result.score()
            result = S
        return

    w = W[i]
    foreach x, y in S.coordinates()
        set w position to (x, y)
        while S.put(w) # check that w doesn't overlap with S's other windows and add it
            fit(W, S, i+1, n, result)
            S.windows.pop()
            w.grow()
        w.restoresize()

Há algumas coisas que devem ser melhoradas:

  • S.coordinates()está muito lento agora. Ele itera todos os pontos S.width x S.heighte verifica se cada um está em uma das janelas de S.

  • S.put()verifica se o seu parâmetro se sobrepõe ao restante das janelas de S fazendo o teste mencionado na resposta de Dave. Talvez isso possa ser melhorado usando árvores de intervalo ?

  • S.score()WS.WEundoWs(hWWW)

  • W

Atualmente, estou tentando descobrir uma estrutura de dados adequada para representar a tela e suas janelas, ele precisa oferecer suporte a essas consultas:

  • retornar uma lista de coordenadas onde uma determinada janela pode ser posicionada sem se sobrepor a outras
  • inserir janela na posição x, y (já verificado que não se sobrepõe)
  • retornar todas as janelas
daniel.jackson
fonte