Dividir un rectángulo en casi cuadrados de áreas dadas

Question

Tengo un juego de norte números positivos y un rectángulo de dimensiones X y Y en el que necesito particionar en norte rectángulos más pequeños de tal manera que:

• El área de superficie de cada rectángulo más pequeño es proporcional a su número correspondiente en el conjunto dado
• Todo el espacio de rectángulo grande está ocupado y no hay espacio sobrante entre rectángulos más pequeños
• Cada rectángulo pequeño debe ser moldeado tan cerca del cuadrado como sea factible
• El tiempo de ejecución debe ser razonablemente pequeño

Necesito instrucciones sobre esto. ¿Conoces un algoritmo de este tipo descrito en la web? ¿Tiene alguna idea (el código de pseudo está bien)?

Gracias.

Answer 1

Lo que describes suena como un treemap:

Treemaps muestran datos jerárquicos (estructurados en árbol) como un conjunto de rectángulos anidados. Cada rama del árbol recibe un rectángulo, que luego se mueve con rectángulos más pequeños que representan sub-ramas. El rectángulo de un nodo de hoja tiene un área proporcional a una dimensión especificada en los datos.

Esa página de Wikipedia enlaces a Una página de Ben Shneiderman, que brinda una buena descripción general y enlaces a las implementaciones de Java:

Luego, mientras desconcertaba esto en el salón de la facultad, ¡tuve el AHA! Experiencia de dividir la pantalla en rectángulos en direcciones horizontales y verticales alternativas a medida que atraviesa los niveles. Este algoritmo recursivo parecía atractivo, pero me tomó unos días convencerme de que siempre funcionaría y escribir un algoritmo de seis líneas.

Wikipedia también para "Treemaps squarified" de Mark Bruls, Kees Huizing y Jarke J. Van Wijk (PDF) que presenta un posible algoritmo:

¿Cómo podemos seleccionar un rectángulo de manera recursiva en rectángulos, de modo que sus relaciones de aspecto (por ejemplo, máxima (altura/ancho, ancho/altura)) se acercan 1 lo más cerca posible? El número de todas las teselaciones posibles es muy grande. Este problema cae en la categoría de problemas np-cuidados. Sin embargo, para nuestra aplicación no necesitamos la solución óptima, se requiere una buena solución que se puede calcular en poco tiempo.

No menciona ninguna recursión en la pregunta, por lo que su situación podría ser solo un nivel de Treemap; Pero dado que los algoritmos funcionan en un nivel a la vez, esto no debería ser un problema.

Answer 2

He estado trabajando en algo similar. Estoy priorizando la simplicidad sobre obtener relaciones de aspecto lo más similares posible. Esto debería (en teoría) trabajar. Lo probé en papel para obtener algunos valores de N entre 1 y 10.

N = número total de rects para crear, q = max (ancho, altura) / min (ancho, altura), r = n / q

Si q> n/2, divida el rect en n partes a lo largo de su lado más largo. Si q <= n/2, divida el rect en r (redondeado int) partes a lo largo de su lado más corto. Luego divida las subrectas en las partes N/R (redondeadas intent) a lo largo de su lado más corto. Resta el valor redondeado del resultado de la siguiente división de subrecciones. Repita para todas las subrectas o hasta que se cree el número requerido de RECTS.