¿Cómo idear un algoritmo para organizar ventanas (redimensionables) en la pantalla para cubrir la mayor cantidad de espacio posible?

20

Me gustaría escribir un programa simple que acepte un conjunto de ventanas (ancho + alto) y la resolución de la pantalla y genere una disposición de esas ventanas en la pantalla de modo que las ventanas ocupen más espacio. Por lo tanto, es posible cambiar el tamaño de una ventana, mientras se mantiene output size >= initial sizey la relación de aspecto. Entonces, para la ventana , me gustaría que el algoritmo devuelva una tupla .( x , y , w i d t hyo(X,y,wyoreth,hmiyosolht)

Creo que esto podría ser una variación de la mochila 2D. Intenté revisar los resultados en la web, pero en su mayoría tenían muchos antecedentes (y ninguna implementación) que me dificultaron seguir.

Estoy menos interesado en el algoritmo más rápido posible, pero más en algo que sea práctico para mi necesidad específica.

daniel.jackson
fuente
1
Si está cambiando el tamaño de una ventana, no está "manteniendo su tamaño inicial", solo su relación de aspecto, supongo.
Emre
1
Puede cambiar el tamaño de una ventana para cubrir la pantalla, ¿cuál es el problema?
2
Secundo el comentario de Saeed. Necesita restricciones adicionales, como tamaños mínimos, el objetivo de minimizar la suma de los cambios de tamaño si desea excluir soluciones triviales. Nota bene: los matemáticos parecen llamar a los problemas de mosaico teselaciones .
Raphael
1
Es mejor decir que desea maximizar el área de ventana visible mínima y minimizar el área de ventana visible máxima, pero ¿se permiten o no conflictos? Edite su pregunta para que no tenga errores, pensar en la declaración actual del problema no es fácil.
2
WminwWsize(w)W

Respuestas:

9

Aunque su pregunta no lo dice, supongo que no desea que las ventanas se superpongan.

Un enfoque para este problema es utilizar un solucionador de restricciones como Choco . Uno simplemente escribe las restricciones que codifican su problema, ajusta el solucionador para que actúe de manera inteligente y luego lo deja correr. Esto significa que todo el pensamiento que necesita hacer se gastará en encontrar una buena manera de codificar el problema, no en idear un algoritmo y hacer la programación y el ajuste. Aquí hay una respuesta parcial para comenzar.

Suponga que el tamaño de la pantalla es .xmax×ymax

Para cada ventana, , tendrá un conjunto de variables x i , y i , h i , w i y restriccionesWixi,yi,hi,wi

  • xi,yi,hi,wi0
  • xi+wixmax
  • yi+hiymax
  • Quizás también algunas restricciones sobre el tamaño mínimo de las ventanas, por ejemplo, y así sucesivamente.hi100
  • Restricciones de aspecto: si la relación de aspecto es 3: 4, la restricción podría ser algo así como , donde ϵ es un pequeño término de error distinto de cero para permitir una ventana no perfecta tamaños, ya que de lo contrario restringiría el problema.4hiϵ3wi4hi+ϵϵ

Ahora debe ocuparse de la superposición de ventanas. Para cada par de ventanas, , donde i j , generará restricciones como las siguientes, que capturan que no aparece ninguna esquina de W j dentro de W i . Para ( x , y ) { ( x j , y j ) , ( x j + w j , y j ) , ( x j , yWi,WjijWjWi , generar restricción:(x,y){(xj,yj),(xj+wj,yj),(xj,yj+hj),(xj+wj,yj+hj)}

  • .¬(xixxi+wjyiyyi+hj)

Las restricciones especificadas hasta ahora solo describen ventanas no superpuestas que no se derraman a los lados de la pantalla, que satisfacen algunas restricciones de tamaño mínimo y que conservan su relación de aspecto.

Para obtener un buen ajuste, debe especificar una métrica que capture lo que significa ser un buen diseño. Una posibilidad es suponer que desea mantener las ventanas aproximadamente del mismo tamaño y / o que desea minimizar el "espacio en blanco". No creo que esto se pueda especificar usando Choco, pero puede ser posible con otra solución de restricción (alguien más podría ayudar aquí).

Choco permite maximizar el wrt a una función objetivo especificada como una sola variable. En base a esta idea, podría maximizar lo siguiente:

  • i(hi+wi)

escribiendo una restricción y diciéndole a Choco que maximice c o s t .cost=i(hi+wi)cost

Dave Clarke
fuente
Esto parece prometedor y definitivamente jugaré con Choco para ver cómo funciona y qué tan rápido.
daniel.jackson
Pero, ¿por qué decirlo en general? Creo que puedes expresar las restricciones como desigualdades lineales, lo que significa que lo que tienes es un programa lineal vainilla.
Suresh
@Suresh: Siéntase libre de elaborar. No veo de inmediato cómo hacerlo.
Dave Clarke
1

Comencé a escribir un prototipo para una solución de fuerza bruta, que espero pueda optimizarse hasta el punto en que sea práctico.

Primero, algunas definiciones: Sea el conjunto de todas las ventanas. Cada ventana w está compuesta por x w , y w , w w , h w para las coordenadas x, y y el ancho y la altura. Una ventana se inicializa con un ancho y una altura mínimos.Wwxw,yw,ww,hw

La entrada del algoritmo es la pantalla, , que tiene un ancho y alto y una lista de ventanas.S

Funciona más o menos así:

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()

Hay algunas cosas que deberían mejorarse:

  • S.coordinates()es muy lento en este momento Repite todos los puntos S.width x S.heighty comprueba si cada uno está en una de las ventanas de S.

  • S.put()comprueba si su parámetro se superpone con el resto de las ventanas de S haciendo la prueba mencionada en la respuesta de Dave. ¿Quizás esto pueda mejorarse usando árboles de intervalos ?

  • S.score()wS.windows(hwww)

  • W

Actualmente estoy tratando de descubrir una estructura de datos adecuada para representar la pantalla y sus ventanas, debe admitir estas consultas:

  • devuelve una lista de coordenadas donde se puede colocar una ventana determinada sin superponerse con otras
  • insertar ventana en la posición x, y (ya verificado que no se superpone)
  • devolver todas las ventanas
revs daniel.jackson
fuente