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 size
y la relación de aspecto. Entonces, para la ventana , me gustaría que el algoritmo devuelva una tupla .( x , y , w i d t h
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.
fuente
Respuestas:
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 restriccionesWi xi,yi,hi,wi
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,Wj i≠j Wj Wi , generar restricción:(x,y)∈{(xj,yj),(xj+wj,yj),(xj,yj+hj),(xj+wj,yj+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:
escribiendo una restricción y diciéndole a Choco que maximice c o s t .cost=∑i(hi+wi) cost
fuente
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.W w xw,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í:
Hay algunas cosas que deberían mejorarse:
S.coordinates()
es muy lento en este momento Repite todos los puntosS.width x S.height
y 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()
Actualmente estoy tratando de descubrir una estructura de datos adecuada para representar la pantalla y sus ventanas, debe admitir estas consultas:
fuente