Algoritmo para dividir un rectángulo en retangles más pequeños?

¿Cuál es el algoritmo para dividir un rectángulo (c struct con 4 int s) en un número aleatorio de rectángulos más pequeños (devolver una lista de struct s)? Aún mejor si la dimensión máxima y mínima de los rectángulos más pequeños se puede controlar mediante un parámetro.Algoritmo para dividir un rectángulo en retangles más pequeños?

p. Ej.

+----------+   +-------+--+ 
|   |   |  | | 
|   |   |  | | 
|   | -->  |---+---+--| (good) 
|   |   | |  | 
|   |   +---+  | 
|   |   | |  | 
+----------+   +---+------+

formas más pequeñas deben ser de 4 lados, los siguientes no es buena:

+----------+   +-------+--+ 
|   |   |  | | 
|   |   |  | | 
|   | -->  |---+---+--| (not good) 
|   |   |   | 
|   |   +---+  | 
|   |   | |  | 
+----------+   +---+------+

Gracias!

Apéndice: (rectángulo para la discusión de Morón)

+----+--------+ 
    | |  | 
    | +---+----+ 
    | | | | (rectangle-chase) 
    +----+---+ | 
    |  | | 
    +--------+----+

Fuente

2010-07-08 ohho

¿Existen restricciones sobre cómo deben estructurarse los rectángulos más pequeños? – andand

No codigo en C, pero me parece que dividir recursivamente rectángulos en 2 rectángulos debería hacer el trabajo. – Mathias

@andand el tamaño del rectángulo más pequeño debe estar restringido por los parámetros límite superior e inferior, es decir, no más pequeño que% del rectángulo padre en el eje x, no mayor que% del rectángulo padre en el eje x, no menor que% el rectángulo padre en el eje y, no más grande que el% del rectángulo padre en el eje y – ohho

Dividir el rectángulo en dos. Recurse.

Fuente

2010-07-08 02:29:57

+1 Muy conciso. –

-1: Te quedarás sin memoria. 1/2 ** inf! = 0 – amphetamachine

@amphetamachine: La condición final aquí es tan obvia que no necesita ser explicada - después de todo, no puedes dividir '1' a la mitad sin tener '0' o algo que no puede ser representado como un entero. –

Elija un punto aleatorio p en un borde y divida el rectángulo con una línea hacia el borde opuesto. A continuación, puede recurse en ambas mitades, deteniendo la recursión al azar o en un límite especificado.

Fuente

2010-07-08 02:35:14 Mandelbrot

Es un poco extraño hacer esta pregunta sin especificar en qué condiciones se dividen los rectángulos.

Sin embargo, sospecho que lo que estás buscando es un árbol kd. El árbol kd es un árbol binario en el que los nodos se dividen con dos nodos secundarios resultantes basados en una condición. http://en.wikipedia.org/wiki/Kd-tree

También hay un árbol cuádruple que puede ser un poco más simple de implementar. Implica dividir nodos en 4 niños de igual tamaño. Cada niño se divide recursivamente de esta forma hasta que se detiene alguna condición. http://en.wikipedia.org/wiki/Quadtree

[Editar:. Actualizado en respuesta a las modificaciones de la OP] Por lo que está haciendo, podría ser más simple para empezar dividiendo el rectángulo en una rejilla uniforme y decidir qué elementos de fusionar? Básicamente, un enfoque ascendente: simplemente elija uno y comience a fusionar las celdas adyacentes al azar. No haga esto para las celdas que ya han sido atravesadas, y la estructura combinada debe tener un ancho y una altura tal que expandir una grilla de 2x1 celdas se expanda a 2x2 o 3x1 para asegurarse de mantener constantemente una forma de rectángulo de 4 lados para el nodo combinado

Si quieres un enfoque más elegante, puedes acercarte a esto como un árbol kd y construirlo de arriba hacia abajo, pero necesitarías unir subárboles enteros a medida que te dividas según las condiciones aleatorias y el mínimo/parámetro de ancho/alto máximo.

Fuente

2010-07-08 03:02:14 stinky472

+1 para kd-trees –

kd-trees tienen el mismo problema que la solución aceptada. Considere el nodo raíz. Si se divide en x, tiene una línea vertical que divide el rectángulo. Si se divide en y, tiene una línea horizontal que divide el rectángulo. De hecho, esta solución no es muy diferente de la aceptada. –

@Moron No veo dónde está el problema con esta solución. Publique una respuesta que describa el problema con las soluciones sugeridas/aceptadas y proporcione la suya propia, omitiendo el problema. No veo el problema porque, dada la pregunta, creo que el operador nunca querría crear algo que se parezca al caso que describió. Entonces, los kd son suficientes para sus propósitos. –

Algoritmo para dividir un rectángulo en retangles más pequeños?

Respuesta

Cuestiones relacionadas