Encontrar áreas libres en forma de rectángulo sin intersección entre rectángulos en C#

Tengo un problema siguiente. Un rectángulo grande contiene rectángulos más pequeños que no se intersecan (los rectángulos negros en la imagen a continuación) y necesito encontrar un algoritmo para llenar el área libre restante con rectángulos que no se intersecan (los rojos en la imagen a continuación). La velocidad no es un problema para el algoritmo. Además, si alguien tuviera un código fuente de ejemplo del algoritmo, realmente lo apreciaría.Encontrar áreas libres en forma de rectángulo sin intersección entre rectángulos en C#

Editar. Pequeña aclaración Necesito obtener las coordenadas de los rectángulos rojos para no dibujarlos. También estoy trabajando con datos de puntos, no imágenes.

http://koti.mbnet.fi/niempi2/Squares.gif

Fuente

2010-08-04 Jargo

¿Comienza con datos de punto o una imagen? –

Datos de punto, es decir, coordenadas de los rectángulos negros en la imagen. También necesito obtener las coordenadas de los rectángulos rojos, no solo dibujarlos. – Jargo

Hay más de una forma de definir un conjunto de rectángulos rojos para un conjunto determinado de rectángulos negros. ¿Te importa qué conjunto se devuelve? –

Al igual que la mayoría de los problemas de empaquetamiento de bandejas, este parece un problema NP-difícil para mí. Con 2 rectángulos, ¡hay 8! (= 40320) arreglos posibles que debe considerar. ¡Tres rectángulos producen 12! posibilidades, un fresco 480 millones.

Necesitará una heurística para hacerlo computable. Más allá de favorecer los bordes exteriores de los rectángulos más cercanos al rectángulo delimitador, no veo uno bueno. Necesitarás requisitos más estrictos en los rectángulos resultantes que aceptas, el número de ellos no ayudará. Me alegro de que este no es mi problema :)

Fuente

2010-08-04 15:36:16

Como dije antes del diseño de los rectángulos no importa y en realidad puedo eliminar el requisito de tener la menor cantidad posible de rectángulos de llenado. Así que realmente no tengo que pasar por todas las soluciones posibles porque simplemente puedo elegir la primera que llena todo el espacio vacío. La solución que estaba pensando era primero calcular los 4 rectángulos de relleno más externos, que es una tarea fácil y después de eso calcular los rectángulos del centro por separado; en este caso, ¡solo tendría 4! arreglos posibles con 2 rectángulos. – Jargo

Parece que ya sabes cómo hacerlo. ¿Por qué preguntaste? –

@Nobugz: ¿Puede por favor decirme cómo calculó 2 rectangles requeriría 8! y 3 requerirían 12 !? –

vistazo a la clase Región.

Fuente

2010-08-04 13:46:17 leppie

por favor, deje de llamar a las personas sin ningún motivo o provocación al volver a formular sus preguntas. Especialmente cuando el error de etiquetado se reduce a un [error] (http://meta.stackexchange.com/questions/59556/tags-with-uppercase-characters-get-cut) –

Aunque hay múltiples soluciones posibles, creo que puede obtener una con bastante facilidad.

Trabajaría en aumentar los valores a lo largo de un eje. Al escanear todos los rectángulos y ordenar las apariencias de sus bordes a lo largo de ese eje, puede caminar a través de ellos y crear rectángulos a medida que avanza. Cada vez que tocas un nuevo par de esquinas, puedes comparar con los rectángulos que tienes actualmente 'abiertos' y determinar qué hacer (cerrarlos, comenzar nuevos, dividir, etc.).

Esa declaración no es una solución completa, pero creo que le lleva de una solución compleja a una simple. Tampoco parece ser NP completa en términos de rendimiento. Incluso podría obtener O (n) perf.

Un problema interesante. Háganos saber cómo le va.

Fuente

2010-08-05 14:48:09

Encontrar áreas libres en forma de rectángulo sin intersección entre rectángulos en C#

Respuesta

Cuestiones relacionadas