algorithm - texto - relleno degradado en excel

Rellena una forma 2D arbitraria con un conjunto dado de rectángulos

Question

Tengo un conjunto de rectángulos y formas arbitrarias en el espacio 2D. La forma no es necesaria un polígono (puede ser un círculo), y los rectángulos tienen diferentes anchuras y alturas. La tarea es aproximar la forma con rectángulos lo más cerca posible. No puedo cambiar las dimensiones de los rectángulos, pero la rotación está permitida.

Suena muy similar al problema del empaque y al problema de cobertura, pero el área de cobertura no es rectangular ...

Supongo que es un problema de NP, y estoy bastante seguro de que debería haber algunos documentos que muestren buenas heurísticas para resolverlo, pero no sé qué buscar en Google. ¿Donde debería empezar?

Actualización: una idea acaba de llegar a mi mente, pero no estoy segura de si vale la pena investigar. ¿Y si consideramos la forma delimitadora como un molde físico lleno de agua? Cada rectángulo se considera como una partícula cargada positivamente con tamaño. Ahora suelta el rectángulo más pequeño. Luego suelta el siguiente por tamaño en un punto aleatorio. Si los rectángulos están demasiado cerca, se repelen entre sí. Sigue agregando rectángulos hasta que todos estén usados. ¿Podría funcionar este método?

Answer 1

Creo que este problema es adecuado para resolver con algoritmo genético y / o algoritmo de estrategia evolutiva. He hecho un problema similar de empaquetado de cajas con la ayuda de algún tipo de algoritmo de estrategia evolutiva. Mira esto en mi blog .

Entonces, si va a utilizar dicho enfoque, codifique en el cuadro de cromosomas:

• coordenada x
• coordenada y
• ángulo

A continuación, intente minimizar dicha función de fitness-

y = w1 * box_intersection_area + w2 * box_area_out_of_shape + w3 * average_circle_radius_in_free_space

Elija los pesos w1, w2, w3 para afectar la importancia de los factores. Cuando el algoritmo genético encuentre una solución parcial (elimine las casillas que aún se superponen entre sí o están fuera de forma) y tendrá al menos una solución legal (pero no necesariamente óptima).

¡Buena suerte en este interesante problema!

Answer 2

Creo que podrías buscar algoritmos de empaquetado y generación automática de diseños. Los algoritmos de generación automática de diseño VLSI pueden necesitar cosas similares, al igual que las preguntas de diseño textil ...

Este documento Hegedüs: Algoritmos para cubrir polígonos por rectángulos parece abordar un problema similar. Y dado que este documento es de 1982, podría ser interesante mirar los documentos que citan este . Además, esta reunión parece estar discutiendo problemas de investigación relacionados con esto, por lo que podría ser un punto de partida para las palabras clave o los nombres que investigan esta idea.

No sé si la investigación de geometría computacional tiene algoritmos para su problema específico, o si estos algoritmos son lo suficientemente fáciles / prácticos de implementar. Aquí es cómo lo abordaría si tuviera que hacerlo sin poder buscar trabajos anteriores. Esto es solo una dirección, de lejos no es una solución ...

Formularlo como un problema de optimización. Tiene variables discretas de los rectángulos que elige (sí o no) y variables continuas (ubicación y orientación de los triángulos). Ahora puede configurar dos optimizaciones independientes: una optimización discreta que selecciona los rectángulos; y un continuo que optimiza para la ubicación y orientación una vez que se dan los rectángulos. Entrelazar estas dos optimizaciones. Por supuesto, la dificultad radica en la formulación de optimizaciones y en el diseño de la energía de error para que no se quede atascado en algunas configuraciones extrañas (mínimos locales). Intentaría obtener el problema continuo de mínimos cuadrados de manera que pueda usar bibliotecas de optimizaciones estándar.

Answer 3

De hecho, es NP difícil y, como tiene una aplicación de alta tecnología, las estrategias aproximadas razonablemente eficientes ni siquiera están en las patentes, y mucho menos en los artículos publicados.

Lo mejor que puede hacer con un presupuesto limitado es comenzar por limitar el problema. Suponga que todos los rectángulos son exactamente iguales. Suponga que todos los rectángulos que son subdivisiones binarias de su rectángulo estándar también están permitidos, ya que puede preempaquetarlos de manera eficiente para que se ajusten a su división central. Para obtener puntos adicionales, también puede formar varios esquemas fijos para pegar rectángulos centrales para cubrir algunas formas más grandes con proporciones sustancialmente diferentes. Suponga que puede cambiar las dimensiones de su rectángulo / celda estándar siempre que el resto (el esquema de empaquetado previo y el encolado) sigan siendo los mismos: esto le brinda parámetros para decidir el tamaño aproximado del rectángulo central en función de los rectángulos que le den.

Ahora puede jugar con las relaciones de aspecto para aproximar el error que tal sistema limitado podría garantizar. Para las primeras iteraciones, suponga que puede tener un error del 50% con un esquema de subdivisión simple y luego cambiar el esquema para reducir el error pero sin aumentar la complejidad asintótica del preembalaje. Al final del día, siempre está asignando rectángulos dados a sus subdivisiones de cuadrícula y binarias precalculadas y ahora fijas, lo que significa que no está tratando de hacer un diseño o retroceso en absoluto, siempre está satisfecho con la primera aproximación encajar en la red.

Trabaje en la definición de clases de rectángulos que combinen bien con su esquema, que de nuevo es para mantener todo el proceso invertido, nunca está tratando de ajustar lo que se le da, está definiendo lo que se le debe dar para que salga bien. Entonces puntúas el resto como error ya que es aproximación.

Luego, puede intentar hacer un poco más, pero no mucho más: cualquier resbalón en retroceso o error pequeño arbitrario de clavado y es exponencial.

Si se encuentra en un centro de investigación y puede obtener algo de tiempo de supercomputadora, realice una serie de búsquedas exhaustivas con mezclas patológicas allí solo para ver cómo se ve el empaque óptimo y para ver si puede derivar algunos esquemas de subdivisión más y / o Clases de conjuntos rectangulares.

Eso debería ser suficiente para los primeros 2 años o investigación :-)