¿Cuántos círculos de un radio determinado se pueden empaquetar en una caja rectangular determinada?

Question

Acabo de volver de mi clase de Matemáticas de Embalaje y Envío, y me he encontrado con un problema que he estado tratando de resolver.

Digamos que tengo un rectángulo de longitud $l$ y el ancho $w$ .

¿Hay una ecuación simple que pueda ser usada para mostrarme cuántos círculos de radio $r$ puede ser empaquetado en el rectángulo, en la manera óptima ? Para que no se superpongan los círculos. ( $r$ es menor que ambos $l$ y $w$ )

Estoy bastante a oscuras en cuanto a cuál es el método óptimo de empaquetar los círculos en el menor espacio posible, para una forma determinada.

Una ecuación con una salida no entera me es útil siempre y cuando el valor truncado (redondeado hacia abajo) sea la respuesta verdadera.

(No estoy tan interesado en cómo los círculos estarían llenos, ya que voy a entrar en el negocio y sólo quiero saber cuánto puedo exigir a los empacadores que contrato para empacar mi producto)

Answer 1

Antes tenía una respuesta, pero he investigado un poco más y mi respuesta era incorrecta, así que la he eliminado. Este enlace puede ser de interés: Empaquetamiento de círculos en un cuadrado (wikipedia)

KennyTM sugirió que tal vez no exista todavía una solución óptima para este problema en general. Al investigar más a fondo, he comprobado que probablemente sea cierto. Mira esta página: Embalaje circular - Embalajes más conocidos . Como se puede ver, se han encontrado soluciones hasta 30 círculos y se ha demostrado que son óptimas. (Otros números mayores de círculos se han demostrado óptimos, pero 31 no)

Obsérvese que aunque el problema definido en la página de la wikipedia y en el otro enlace es superficialmente diferente a la pregunta planteada aquí, se está planteando la misma pregunta fundamental, que es "¿cuál es la forma más eficiente de empaquetar círculos en un contenedor cuadrado/rectangular?".

...Y parece que la respuesta es "no lo sabemos realmente" :)

Answer 2

Anidación de círculos en hojas rectangulares

Anidación óptima y límites prácticos: Cuando se consideran diferentes opciones de anidación mientras se busca una solución de anidación óptima, es deseable encontrar la solución rápidamente. Esto plantea la siguiente pregunta: ¿cómo sé que una solución es óptima? La respuesta no siempre es obvia.

Parte de la respuesta es una búsqueda automatizada de anidamiento, que puede explorar una serie de opciones de forma rápida y automática e informar de los resultados. Encontrar el número máximo de piezas en una hoja completa o encontrar la hoja de menor tamaño necesaria para un número determinado de piezas. Hay que tener en cuenta que los círculos tienen sutiles matices en la eficiencia del embalaje. Puede ser una ventaja tener un conocimiento práctico de estas eficiencias de embalaje esperadas de los casos típicos. (Véase el gráfico de eficiencia)

Curiosamente, en algunos casos el empaquetamiento óptimo de los círculos es un empaquetamiento irregular, lo que es contrario a la intuición. La transferencia de estos tipos irregulares de empaquetamiento a otro software es difícil. Por lo tanto, generalmente se hace una compensación seleccionando el más óptimo de los patrones de empaquetamiento de círculos más regulares.

Embalaje rectangular, hexagonal y en el peor de los casos

No existe una fórmula fija para calcular el número máximo de discos de una hoja rectangular. La eficacia del empaquetado de discos depende de la disposición de los discos en el material. La disposición rectangular de los discos (con espaciado cero) es del 78,5% (no sufre la baja eficiencia de los efectos de los bordes) El conjunto de discos hexagonales (con espaciado cero) es del 90,6%. El peor caso de empaquetamiento de discos es (2 discos dentro de un cuadrado) 53,8%.

Software de empaquetado en círculo

El software de empaquetado de discos anterior calcula y compara ocho métodos de empaquetado diferentes y destaca las soluciones más eficaces. Cada variación utiliza un patrón de anidamiento diferente. Tenga en cuenta que ningún método por sí solo dará el rendimiento óptimo para anidar cada tamaño de disco en cada tamaño de hoja. El método óptimo varía en función del tamaño de los discos y de las dimensiones de las hojas. Tenga en cuenta que transferir estas disposiciones óptimas de las posiciones x,y de cada disco al software de creación de perfiles puede ser un reto.

Diferentes opciones de anidación examinadas por el software

Diferentes opciones de anidamiento examinadas por el software al buscar la cantidad óptima por hoja.

Un gráfico de la eficacia de la anidación en función del diámetro del disco

Gráfico de la eficiencia de anidamiento (%) frente al diámetro del disco (mm) anidado en una lámina rectangular de 2400x1200 con una separación de 5 mm. La línea azul es la eficacia real y los demás colores son teóricos. Se toma el valor máximo de los resultados de 8 métodos diferentes de empaquetado en círculo. La naturaleza no lineal del gráfico indica que es poco probable que exista una fórmula sencilla para el número máximo de discos. Obsérvese también la baja eficacia de empaquetado de los discos de menos de 100 mm de diámetro, debido a que el espacio entre las partes es un porcentaje mayor del área y la eficacia alcanza un máximo del 78,5%.

Durante la tabulación se anotó el resultado del empaquetado junto con el método de empaquetado en círculo. Además de estos resultados generados automáticamente, si la eficiencia de ese punto de datos parecía baja en comparación con los puntos cercanos del gráfico, se intentaba anidar manualmente los discos y cualquier rendimiento mejor se tabulaba y se anotaba como empaquetamiento irregular. El uso de estos resultados en un sentido práctico ayuda a detener la búsqueda con confianza si la adición de otro disco (N+1) requiere una eficiencia que, según el gráfico, no es posible. La eficiencia máxima de empaquetamiento de discos en rectángulos se investiga y mejora continuamente. Para conocer el mejor nido actual de discos para empaquetado irregular, consulte el enlace en línea: http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html

McErlean, P. (2018) "El manual de programación CAD/CNC: Optimización de materiales 2D y consejos para el corte por láser, plasma y oxicorte"

Answer 3

Este es un conjunto de ecuaciones que se me ocurrió para averiguar cuántos círculos caben en un rectángulo si están escalonados. Espero que os sirva de ayuda.

A= número entero #1 B= resto #1 C= espacio extra entre cada círculo D= diámetro de los círculos E= altura escalonada de las nuevas capas F= % inverso del nuevo círculo respecto al antiguo G= número entero #2 H= altura del rectángulo I= resto #2 J= número entero #3 K= resto #3 L= número total de filas M= número entero #4 N= resto #4 O= total de círculos en filas grandes P= total de círculos en filas pequeñas Q= número total de círculos R= radio de los círculos W= ancho del rectángulo

1 . (W/D) = A,B

2 . [B/(A-1)] = C

3 . [(D)^2-(1/2C+R)^2] = E^2

4 . (D/E) = F

5 . [(H-D)/D] = G,I

6 . (F*G) = J,K

7 . (J+1) = L

8 . (L/2) = M,N

9 . [(M+N)*A] = O

10 . [M*(A-1)] = P

11 . (O+P) = Q