algorithm - ¿Cuántos cuadrados se pueden empaquetar en un círculo?
math language-agnostic (4)
¿Cuántos cuadrados de tamaño a × a se pueden empaquetar en un círculo de radio R ?
No necesito una solución. Solo necesito algún tipo de idea inicial.
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.
Entonces, su primer paso debe ser refinar su pregunta y plantear su problema con mayor precisión.
Rasterice el círculo usando algo así como el algoritmo del círculo de punto medio . 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 cambie el resultado. Dejaré la respuesta aquí ya que puede proporcionar un punto de partida útil para una solución exacta.
Solo un tiro en la oscuridad después de unos minutos de reflexión ...
¿Qué pasa si trabajó con la mitad del círculo y lo dobló 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 tenga sentido ... Está en mi cabeza y parece un poco difícil de articular :)
EDITAR: Después de dibujarlo, creo que este método funcionaría con un pequeño 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.
Me disculpo 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 el ancho o la altura de los cuadrados que está empacando y r es el radio del círculo en el que está 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).
Entonces, 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.
Entonces, consideremos una solución que existe para todos los círculos, echemos un vistazo al cuadrado más grande que podemos caber dentro del círculo.
El cuadrado más grande que puede caber dentro del círculo tiene 4 puntos en el perímetro, y tiene un ancho y una longitud de sqrt(2) * radius (usando el teorema de Pitágoras y usando el 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 especificó, lo que nos dará al menos una solución al problema. Entonces tienes una grilla de sqaures dentro de este cuadrado máximo. La cantidad de cuadrados que puede caber en una fila de esta cuadrícula es
floor((sqrt(2) * radius)/ L)
Y esta solución mínima afirma que puedes tener al menos
Lower Limit = floor((sqrt(2) * radius)/ L) pow 2
número de cuadrados dentro del círculo.
Entonces, en caso de que se pierda, lo único que hice fue tomar el cuadrado más grande que pudiera caber dentro del círculo y luego empacar la mayor cantidad posible de cuadrados en una cuadrícula regular dentro de ese, para darme al menos una solución.
Si obtienes una respuesta en 0 para esta etapa, entonces no puedes encajar 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 empacar 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 mejor solución, use los teóricos como guía para saber qué tan cerca está de lo mejor teórico.
Y si te preocupas por 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 un poco más del 25% del cuadrado interior con 1 cuadrado relleno, lo que significa que obtiene una cobertura aproximada del 20%