c# - una - ¿Cómo llenar un cuadrado con cuadrados/rectángulos más pequeños?

metodo para dibujar en c#

Question

En mi oficina en el trabajo, no se nos permite pintar las paredes, por lo que he decidido enmarcar cuadrados y rectángulos, pegarles una tela bonita y colocarlas en la pared.

Estoy tratando de escribir un método que tome mis dimensiones de entrada (9 ''x 8'' 8 ") y tamaño mínimo / máximo (1 ''x 3'', 2 '', 4'', etc.) y genere un patrón aleatorio de Cuadrados y rectángulos para llenar la pared. Intenté hacerlo a mano, pero no estoy contento con el diseño que obtuve, y me lleva unos 35 minutos cada vez que quiero "aleatorizar" el diseño.

Answer 1

1. Definir área de entrada;
2. Dibuja líneas verticales en varias ubicaciones horizontales aleatorias a través de toda la altura;
3. Dibuja líneas horizontales en varias posiciones verticales a través de todo el ancho;
4. Mueva algunas "columnas" hacia arriba o hacia abajo en cantidades arbitrarias;
5. Desplace algunas "filas" hacia la izquierda o hacia la derecha por cantidades arbitrarias (puede ser necesario subdividir algunas celdas para obtener costuras horizontales completas);
6. Eliminar las costuras según sea estéticamente requerido.

Este método gráfico tiene similitudes con la respuesta de Brian .

Answer 2

Construyendo a partir de la respuesta de Philippe Beaudoin.

Existen implementaciones de treemap en otros idiomas que también puede utilizar. En Ruby con RubyTreeMap podías hacer

require ''Treemap''
require ''Treemap/image_output.rb''
root = Treemap::Node.new 0.upto(100){|i| root.new_child(:size => rand) }
output = Treemap::ImageOutput.new do |o|
o.width = 800
o.height = 600
end
output.to_png(root, "C:/output/test.png")

Sin embargo, ordena los rectángulos, por lo que no parece muy aleatorio, pero podría ser un comienzo. Ver rubytreemap.rubyforge.org/docs/index.html para más información

Answer 3

Embalaje de la papelera o embalaje cuadrado?

Embalaje de contenedores: http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

Embalaje cuadrado: http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html

En realidad, esto suena más como una demostración de pintura cuadrada aleatoria de la vieja escuela, alrededor de los días de computación de 8 bits, especialmente si no le importa superponerse. Pero si quieres ser especialmente geek, crea cuadrados al azar y resuelve el problema del empaque.

Answer 4

Otra idea:

1. Randomly generate points on the wall
Use as many points as the number of rectangles you want
Introduce sampling bias to get cooler patterns
2. Build the kd-tree of these points

El árbol kd dividirá el espacio en varios rectángulos. Puede que haya demasiada estructura para lo que quieres, pero sigue siendo un algoritmo geek ordenado.

(ver: http://en.wikipedia.org/wiki/Kd-tree )

Edit: solo miré JTreeMap, se parece un poco a esto, es lo que está haciendo.

Answer 5

Si está hablando de un problema de programación puro;) Existe una técnica llamada Bin Packing que intenta empaquetar un número de contenedores en el área más pequeña posible. Hay un montón de material por ahí

http://en.wikipedia.org/wiki/Bin_packing_problem

http://mathworld.wolfram.com/Bin-PackingProblem.html

http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

Así que ''podría'' crear una carga de cuadrados al azar y ejecutarlo a través de un empaquetador bin para generar su patrón.

No he implementado un algoritmo de empaquetado de contenedores, pero lo he visto realizado por un colega para un sitio web de Nike. La mejor de las suertes

Answer 6

Suena como un Treemap

Answer 7

Una solución es comenzar con los cuadrados x * y y combinarlos al azar para formar rectángulos. Querrá asignar pesos diferentes a cuadrados de diferentes tamaños para evitar que el algoritmo termine con montones de rectángulos diminutos (es decir, los rectángulos grandes probablemente deberían tener una mayor probabilidad de ser seleccionados para fusionarse hasta que se vuelvan demasiado grandes).

Answer 8

Ya que puedes elegir el tamaño de los rectángulos, esto no es un problema difícil.

Yo diría que puedes hacer algo tan simple como:

Pick an (x,y) coordinate that is not currently inside a rectangle. Pick a second (x,y) coordinate so that when you draw a rectangle between the two coordinates, it won''t overlap anything. The bounding box of valid points is just bounded by the nearest rectangles'' walls. Draw that rectangle. Repeat until, say, you have 90% of the area covered. At that point you can either stop, or fill in the remaining holes with as big rectangles as possible.

Podría ser interesante parametrizar la generación de puntos y luego hacer un algoritmo genético. La función de acondicionamiento físico será la forma en que le guste el arreglo: dibujaría cientos de arreglos para usted, y los calificaría en una escala de 1 a 10. Luego tomará las mejores y las modificará, y repita hasta que obtenga un arreglo que realmente le guste.

Answer 9

Yo generaría todo en una espiral entrando lentamente. Si en algún punto llega a un punto donde se demuestra que su solución no tiene solución (IE, no puede poner ningún cuadrado en el centro restante para satisfacer las restricciones), vaya a Un borrador anterior y cambiar algún cuadrado hasta que encuentre una solución feliz.

Pseudocódigo se vería algo así como:

public Board GenerateSquares(direction, board, prevSquare)
{
Rectangle[] rs = generateAllPossibleNextRectangles(direction, prevSquare, board);
for(/*all possible next rectangles in some random order*/)){
if(board.add(rs[x]){
//see if you need to change direction)
Board nBoard = GenerateSquares(direction, board, rs[x]);
if(nBoard != null) return nBoard; //done
else board.remove(rs[x]);
}
}
//all possibilities tried, none worked
return null;
}

}

Answer 10

Yo sugiero:

Comience por configurar un polígono con cuatro vértices que se comen en trozos rectangulares de tamaño variable (hasta el lado máximo):

public double[] fillBoard(double width, double height, double maxside) {
double[] dest = new int[0];
double[] poly = new int[10];
poly[0] = 0; poly[1] = 0; poly[2] = width; poly[3] = 0;
poly[4] = width; poly[5] = height; poly[6] = 0; poly[7] = height;
poly[8] = 0; poly[9] = 0;
...
return dest; /* x,y pairs */
}

Luego elija un vértice aleatorio, busque líneas de polígono dentro de (incluido) 2 X lado máximo de la línea. Encuentre los valores de x de todas las líneas verticales y los valores de y de todas las líneas horizontales. Cree calificaciones para la "bondad" de elegir cada valor x e y, y ecuaciones para generar calificaciones para valores entre los valores. La bondad se mide como la reducción del número de líneas en el polígono restante. Genere tres opciones para cada rango de valores entre dos coordenadas x o dos coordenadas y, utilizando un generador pseudoaleatorio. Califique y elija pares de valores de x y par de y sobre la base del promedio ponderado que se inclina hacia buenas opciones. Aplique el nuevo rectángulo a la lista cortando su forma de la matriz de polietileno y agregando las coordenadas del rectángulo a la matriz de destino.

La pregunta no establece un parámetro lateral mínimo. Pero si se necesita uno, el algoritmo (al golpear un enganche con un espacio demasiado pequeño) no debe incluir candidatos demasiado pequeños en las listas de selección (lo que ocasionalmente los dejará vacíos) y deseleccionará un número de los rectángulos circundantes en un cierto radio de problema con el tamaño y realizar nuevos intentos de regeneración de esa área, y con suerte el área del problema, hasta que se cumplan los criterios. La recursión puede eliminar áreas cada vez más grandes si falla una retransmisión más pequeña de los azulejos.

EDITAR

Hacer algunas pruebas de éxito para eliminar posibles superposiciones. Y come un poco de espinaca antes de comenzar a escribir. ;)