¿Cuántos cuadrados se pueden empaquetar en un círculo?

Question

¿Cuántos cuadrados de tamaño un × un pueden ser empacados en un círculo de radio R ?

No necesito una solución. Solo necesito algún tipo de idea inicial.

Answer 1

Pido disculpas por escribir una respuesta tan larga. Mi enfoque es comenzar con un máximo teórico y un mínimo garantizado. Cuando aborda el problema, puede usar estos valores para determinar qué tan bueno es el algoritmo que usa. Si puede pensar en un mínimo mejor, entonces puede usar eso en su lugar.

Podemos definir un límite superior para el problema simplemente usando el área del círculo

Upper Limit = floor((PI * (r pow 2))/(L * L)) 

donde L es la anchura o la altura de los cuadrados que está embalaje y r es el radio del círculo que están empacando los cuadrados. Estamos seguros de que este es un límite superior porque a) debemos tener un número discreto de casillas yb) no podemos ocupar más espacio que el área del círculo. (Una prueba formal funcionaría en algún lugar en la línea de asumir que teníamos una caja más que esta, entonces la suma del área de las cajas sería mayor que el área del círculo).

Por lo tanto, con un límite superior en la mano, ahora podemos tomar cualquier solución que exista para todos los círculos y llamarla una solución mínima.

Así que, consideremos una solución que existe para todos los círculos, echando un vistazo al cuadrado más grande que podemos caber dentro del círculo.

la plaza más grande que puede caber dentro del círculo tiene 4 puntos en el perímetro, y tiene una anchura y longitud de sqrt(2) * radius (usando el teorema de Pitágoras y el uso de la radio para la longitud de los bordes más cortos)

Entonces, lo primero que notamos es que si sqrt(2) * radius es menor que la dimensión de sus cuadrados, entonces no puede caber ningún cuadrado en el círculo, porque después de todo, este es el cuadrado más grande que puede caber.

Ahora podemos hacer un cálculo sencillo para dividir este gran cuadrado en una cuadrícula regular de cuadrados usando la L que usted especificó, lo que nos dará al menos una solución al problema. Entonces tienes una grilla de sqaures dentro de este cuadrado máximo. El número de cuadrados que puede caber en una sola fila de esta esta rejilla es

floor((sqrt(2) * radius)/ L) 

Y por lo que esta solución mínima afirma que se puede tener al menos

Lower Limit = floor((sqrt(2) * radius)/ L) pow 2 

número de plazas en el interior del círculo.

Así que en caso de que te pierdas, lo único que hice fue tomar el cuadrado más grande que pudiera caber dentro del círculo y luego empacar tantos cuadrados como fuera posible dentro de una cuadrícula normal, para darme al menos una solución.

Si obtiene una respuesta en 0 para esta etapa, entonces no puede caber ninguna casilla dentro del círculo.

Ahora armado con un máximo teórico y un mínimo absoluto, puede comenzar a probar cualquier tipo de algoritmo heurístico que desee para el embalaje de cuadrados. Un algoritmo simple sería simplemente dividir el círculo en filas y ajustar tantos cuadrados como sea posible en cada fila. A continuación, puede tomar este mínimo como una guía para asegurarse de que se le ocurrió una mejor solución. Si desea gastar más poder de procesamiento buscando una solución mejor, use los teóricos como guía para saber qué tan cerca está de la mejor teoría.

Y si te importa esto, podrías averiguar qué te ofrece el porcentaje teórico máximo y mínimo del algoritmo mínimo que ideé. El cuadrado más grande siempre cubre una proporción fija (pi/4 o alrededor del 78.5% del área interna del círculo, creo). Entonces el mínimo teórico máximo es 78.5% de cobertura. Y el mínimo teórico mínimo no trivial (es decir, distinto de cero) es cuando solo puede caber 1 cuadrado dentro del cuadrado más grande, lo que sucede cuando los cuadrados que está empacando son 1 más grandes que la mitad del ancho y la altura del cuadrado más grande que puede encajar en el círculo. Básicamente, ocupa poco más del 25% del cuadrado interior con 1 cuadrado relleno, lo que significa que obtiene una cobertura aproximada del 20%

Answer 2

Puede empacar tantos cuadrados como desee en un círculo. Si dudas de esta afirmación, dibuja un círculo grande en un pedazo de papel, luego dibuja un cuadrado con una longitud lateral de 10^(- 18) m dentro, repite. Cuando te acerques al límite del círculo, comienza a dibujar cuadrados con una longitud lateral de 10^(- 21) m.

Así que su primer paso debe ser refinar su pregunta y plantear su problema con mayor precisión.

Answer 3

Sólo un tiro en la oscuridad después de unos minutos de pensamiento ...

¿Qué pasa si usted trabajó con la mitad del círculo y doblado al final. Comenzaría con una cuadrícula de cuadrados de la longitud del diámetro y el ancho del radio, cubriendo esencialmente el semicírculo. Luego revisa las 4 esquinas de cada cuadrado y asegúrate de que sus coordenadas estén dentro del radio del círculo. Esto, por supuesto, requeriría que trace el círculo y los cuadrados en algún tipo de sistema de coordenadas o cuadrícula.

espero que esto tiene sentido ... Está en mi cabeza y me parece un poco difícil de articular :)

EDIT: Después de dibujar hacia fuera, creo que este método funcionaría con un poco de ajuste. Me gustaría alinear los cuadrados a lo largo del diámetro, pero deslice el primero hacia abajo hasta que encaje. Ponlo en su lugar y comienza a alinear los cuadrados al lado hasta que ya no quepan. Muévase al borde de esta línea de cuadrados y repita los mismos pasos hasta que las filas de cuadrados alcancen el radio.

Answer 4

Rasterice el círculo usando algo como midpoint circle algorithm. La cantidad de píxeles llenos es la cantidad de cuadrados que puede caber en el círculo. Por supuesto, ya que no estás llenando los píxeles, solo contándolos, esto debería llevar un tiempo proporcional a la circunferencia del círculo, no a su área.

Deberá elegir cuidadosamente el radio para la rasterización, de modo que solo cuente los píxeles que están estrictamente dentro del círculo.

Editar: Esto puede no ser exactamente correcto, ya que es posible que la aplicación de un desplazamiento subpíxel a la cuadrícula podría cambiar el resultado. Dejaré la respuesta aquí ya que puede proporcionar un punto de partida útil para una solución exacta.