Tengo un panel de tamaño X por Y. Quiero colocar hasta N rectángulos, de tamaño aleatorio, sobre este panel, pero no quiero que ninguno de ellos se superponga . Necesito saber las posiciones X, Y para estos rectángulos.Coloque rectángulos aleatorios que no se superpongan en un panel
Algoritmo, ¿alguien?
Editar: Todos los N rectángulos son conocidos desde el principio y pueden seleccionarse en cualquier orden. ¿Eso cambia el procedimiento?
Puede modelar esto mediante un conjunto de rectángulos "libres", empezando por uno solo con coordenadas de 0,0, tamaño (x, y). Cada vez que necesite agregar un rectángulo más, elija uno de los rectángulos "libres" restantes, genere un nuevo rectángulo (con una coordenada superior y un tamaño tal que quede totalmente contenido), y divida ese rectángulo, así como cualquier otra superposición " "rectángulo libre", de modo que los niños expresen el espacio libre restante. Esto dará como resultado de 0 a 4 nuevos rectángulos (0 si el rectángulo nuevo es exactamente del tamaño del antiguo rectángulo libre, 4 si está en el medio y así sucesivamente). Con el tiempo, obtendrás cada vez más áreas libres más pequeñas y más pequeñas, por lo que los rectángulos que crees también serán más pequeños.
Ok, no es una explicación muy elaborada, es más fácil de mostrar en la pizarra. Pero el modelo es uno que utilicé para encontrar la ubicación inicial para los componentes de interfaz gráfica de usuario recién cortados; es fácil hacer un seguimiento de los trozos de pantalla disponibles y elegir (por ejemplo) el área superior izquierda o superior.
Implementé esto y funciona muy bien.También agregué la fusión de los rectángulos libres para evitar el problema cada vez más pequeño. –
@TomerPintel, ¿cómo fusionó los rectángulos libres? Puedo hacerlo visualmente muy fácilmente pero no puedo imaginarme dónde comenzar a hacerlo algorítmicamente. – dataduck
@dataduck, para cada rectángulo libre, repase todos los otros rectángulos libres. Compruebe si su Izquierda, Ancho son iguales y si la Parte inferior de uno es igual a la parte superior de la otra. Si todos son verdaderos, significa que tenemos dos rectángulos libres uno encima del otro. Cree un nuevo rectángulo que contenga estos dos rectángulos con el mismo ancho pero con la altura combinada de los dos existentes. Elimine los rectángulos viejos de la lista y agregue uno nuevo nuevo en su lugar. –
Aquí es un artículo decente en algoritmos de embalaje 2d: http://www.devx.com/dotnet/Article/36005
Por lo general, querrá algún tipo de algoritmo utilizando la heurística para conseguir resultados decentes. Una solución simple (pero no óptima) sería el primer algoritmo de ajuste.
Lamentablemente, este artículo parece estar fuera de línea, devuelve un 404. Si alguien sabe cómo encontrar una actualización, ¡edite la respuesta! – JBCP
O mantenga una lista de rectángulos ya agregados y cree un algoritmo que adivine dónde colocar el nuevo rectángulo basado en esa lista. Puede crear una clase Rectangle básica para contener la información sobre sus rectángulos.
No debería ser tan difícil crear un algoritmo personalizado.
cada vez que alguien dice "no debería ser tan difícil", deberían mostrar el código. – willc2
Utilicé este Rectangle Packing algorithm en una de mis aplicaciones, disponible como archivos fuente C#.
El algoritmo se inicializa con el tamaño del panel, luego itera por todos los rectángulos y obtiene su posición. El orden de los rectángulos puede influir en el resultado, dependiendo del empacador.
Le aconsejaría que utilice la sugerencia de StaxMans.
Aquí es mi 2c:
Añadir un montón de rectángulos al azar (superpuestos entre sí). eliminar rectángulos superpuestos:
for rectangle in list of rectangles:
if rectangle not deleted:
delete all rectangles touching rectangle.
permite encontrar todos los rectángulos que tocan un rectángulo en particular, se puede utilizar un árbol quad o las desigualdades basadas en x1, x2 y1, y2 valores.
Editar: De hecho, la mayoría de los motores de juegos como pygame etc. incluyen la detección de colisiones de rectángulos, que es un problema común.
http://gamedev.stackexchange.com/questions/6730/how-to-randomly-place-rectangle-inside-a-larger-bounding-rectangle-without-inter –