algorithm - español - qgis girona

Posicionando cuadrados en un círculo con diámetro mínimo.

Question

Dados n cuadrados con una longitud de borde l , ¿cómo puedo determinar el radio mínimo r del círculo para poder distribuir todos los cuadrados uniformemente a lo largo del perímetro del círculo sin que se superpongan? (Restricción: el primer cuadrado siempre se colocará a las 12 en punto.)

Pregunta de seguimiento: ¿Cómo puedo colocar n rectángulos idénticos con altura hy ancho w ?

ejemplo http://pub.n3rd.org/circle.png

Answer 1

Asumamos que resolviste el problema para 3 o 4 cuadrados.

Si tiene n > = 5 cuadrados y coloca un cuadrado en la parte superior del círculo, tendrá otro cuadrado caer en el primer cuadrante de un plano cartesiano concéntrico con su círculo.

El problema es entonces encontrar un radio r para el círculo tal que el lado izquierdo del círculo al lado del círculo superior y el lado derecho del círculo superior no se "crucen" entre sí.

La coordenada x del lado derecho del círculo superior es x1 = L / 2, donde L es el lado de un cuadrado. La coordenada x del lado izquierdo del círculo al lado del círculo superior es x2 = r cos a - L / 2, donde r es el radio y a es el ángulo entre cada par de centros cuadrados ( a = 360 / n grados) .

Así que necesitamos resolver x1 <= x2 , lo que lleva a

r > = L / cos a .

L y a son conocidos, así que hemos terminado :-)

Answer 2

Calcularía un límite superior del radio mínimo, trabajando con círculos que encierran los cuadrados en lugar de con los cuadrados mismos.

Los resultados de mi cálculo en:

Rmin <= X / (sqrt (2) * sin (180 / N))

Donde: X es la longitud del lado del cuadrado y N es el número requerido de cuadrados.

Supongo que los círculos están posicionados de tal manera que sus centros caen en la circunferencia del círculo grande.

- EDITAR -

Usando la idea de Dave en el comentario a continuación, también podemos calcular un límite inferior agradable, considerando que los círculos están dentro de los cuadrados (por lo tanto, tienen un radio X / 2). Este límite es:

Rmin> = X / (2 * sin (180 / N))

Answer 3

Comienza con un círculo arbitrario (por ejemplo, con un diámetro de (* nl) ) y coloca los cuadrados de manera uniforme en la circunferencia. Luego pasas por cada par de cuadrados adyacentes y:

• calcular la línea recta que conecta sus puntos medios,

• calcule la intersección de esta línea con los lados cuadrados intermedios (M1 y M2 son los puntos medios, S1 y S2 las intersecciones correspondientes con el lado cuadrado)

                  S2         S1
  M1--------------*----------*---------------M2
  
  ------------------------
  |                      |
  |                      |
  |                      |
  |                      |
  |          M1          |
  |           /          |
  |            /         |
  |      -------*------- +--------
  |      |       /       |       |
  |      |        /      |       |
  -------+---------*------       |
         |          /            |
         |           M2          |
         |                       |
         |                       |
         |                       |
         |                       |
         -------------------------

• calcule el factor de escala que necesitaría para hacer que S1 y S2 caigan juntos (simplemente la relación de la suma de M1-S1 y S2-M2 a M1-M2), y

Finalmente escalar el círculo por el máximo de los factores de escala encontrados.

Edición: Esta es la solución exacta. Sin embargo, un poco de pensamiento puede optimizar esto aún más para la velocidad:

• Solo necesita hacer esto para los cuadrados más cercanos a 45 ° (si n es par) resp. 45 ° y 135 ° (si n es impar; en realidad, puede probar que solo uno de estos es necesario).
• Para n grande, el espaciado óptimo de los cuadrados en el círculo se aproximará rápidamente a la longitud de una diagonal de un cuadrado. Por lo tanto, podría calcular los factores de escala para unas pocas n (hasta aproximadamente una docena), y luego tener una aproximación lo suficientemente buena con la diagonal.

Answer 4

Como ya se señaló, el problema de colocar n puntos equidistantes alrededor de la circunferencia de un círculo es trivial. La parte (no terriblemente) difícil del problema es averiguar el radio del círculo necesario para dar un diseño agradable de los cuadrados. Le sugiero que siga una de las otras respuestas y piense que los cuadrados están dentro de un ''buffer'' circular lo suficientemente grande como para contener el cuadrado y el espacio suficiente para satisfacer sus requisitos estéticos. Luego, verifique la fórmula para la longitud del acorde entre los centros de los cuadrados vecinos. Ahora tiene el ángulo, en el centro del círculo, subtendido por el acorde entre los centros cuadrados, y puede calcular fácilmente el radio del círculo desde la trigonometría de un triángulo.

Y, en cuanto a su pregunta de seguimiento: le sugiero que resuelva el problema para los cuadrados de longitud de lado min(h,w) en un círculo, luego transforme los cuadrados en rectángulos y el círculo en una elipse con excentricidad h / w ( o w / h).

Answer 5

Yo lo resolvería así:

Para encontrar la relación entre el radio r y la longitud l analicemos la representación sin dimensiones

• obtener los centros en un círculo (x1, y1) .. (xn, yn)
• desde cada centro, obtenga la esquina inferior derecha de la i-ésima cuadrada y la esquina superior izquierda de i + 1 ª cuadrada
• los dos puntos deben tener igual x o igual y, el que sea menor l
• El procedimiento debe repetirse para cada centro y el que produzca la menor l es la solución final.

Esta es la solución óptima y puede resolverse en términos de r = f (l). La solución se puede adaptar a los rectángulos ajustando la fórmula para xLR [i] y yUL [i + 1].

Intentaré dar algún pseudo código.

EDITAR:
Hay un error en el procedimiento, la parte inferior derecha y la parte superior izquierda no son necesarios puntos cercanos para dos cuadrados / rectángulos adyacentes.

Answer 6

Puede haber una manera matemáticamente inteligente de hacer esto, pero no lo sabría. Creo que es un poco complicado por el hecho de que la geometría es diferente para cada número diferente de cuadrados; para 4 es un rombo, para 5 es un pentágono y así sucesivamente.

Lo que haría es colocar esos cuadrados en un círculo de 1 unidad (demasiado pequeño, lo sé, soporta conmigo) distribuido igualmente en él. Eso es bastante fácil, solo subtitula (divide) tus 360 grados por el número de cuadrados. Luego solo prueba todos tus cuadrados para superponerse contra sus vecinos; si se superponen, aumentar el radio.

Puede hacer que este procedimiento sea menos estúpido de lo que parece utilizando un algoritmo inteligente para aproximarse al tamaño correcto. Estoy pensando en algo como el algoritmo de Newton: dadas dos conjeturas sucesivas, de las cuales una es demasiado pequeña y la otra es demasiado grande, su siguiente conjetura debe ser el promedio de esas dos.

Puede iterar hasta la precisión que desee. Deténgase siempre que la distancia entre conjeturas sea menor que un pequeño margen de error arbitrario.

EDITAR Tengo una mejor solución:

Estaba pensando en qué decirte si preguntas "¿cómo sabré si los cuadrados se superponen?" Esto me dio una idea de cómo calcular exactamente el tamaño del círculo en un solo paso:

Coloca tus cuadrados en un círculo demasiado pequeño. Usted sabe cómo: Calcule los puntos en el círculo donde sus ángulos de 360 ​​/ n lo intersectan, y coloque allí el centro del cuadrado. En realidad, no es necesario que coloques cuadrados aún, los siguientes pasos solo requieren puntos medios.

Para calcular la distancia mínima de un cuadrado a su vecino: Calcule la diferencia en X y la diferencia en Y de los puntos medios, y tome el mínimo de esos. Las X y las Y son en realidad solo cosenos y senos en el círculo.

Querrás el mínimo de cualquier cuadrado contra su vecino (en el sentido de las agujas del reloj, por ejemplo). Por lo tanto, debes recorrer el círculo para encontrar el más pequeño.

La distancia mínima (X o Y) entre los cuadrados debe convertirse en 1.0. Tan solo toma el recíproco de la distancia mínima y multiplica el tamaño del círculo por eso. Presto, tu círculo es del tamaño correcto.

EDITAR

Sin perder generalidad, creo que es posible concretar un poco mi solución para que esté cerca de la codificación. Aquí hay un refinamiento:

• Suponga que los cuadrados tienen tamaño 1, es decir, cada lado tiene una longitud de 1 unidad. Al final, sus cajas seguramente serán más grandes que 1 píxel, pero es solo una cuestión de escala.

• Deshazte de los casos de la esquina:

  if (n < 2) throw new IllegalArgumentException();
  if (n == 2) return 0.5; // 2 squares will fit exactly on a circle of radius 0.5

• Comience con un tamaño de círculo r de 0.5, que seguramente será demasiado pequeño para cualquier número de cuadrados> 2.

  r = 0.5;
  dmin = 1.0; // start assuming minimum distance is fine
  a = 2 * PI / n;
  for (p1 = 0.0; p1 <= PI; p1+=a) { // starting with angle 0, try all points till halfway around
     // (yeah, we''re starting east, not north. doesn''t matter)
     p2 = p1 + a; // next point on the circle 
     dx = abs(r * cos(p2) - r * cos(p1))
     dy = abs(r * sin(p2) - r * sin(p1))
     dmin = min(dmin, dx, dy)
  }
  
  r = r / dmin;

EDITAR

Convertí esto en un código Java real y obtuve algo muy similar a este para ejecutar. Código y resultados aquí: http://ideone.com/r9aiu

Creé salida gráfica utilizando GnuPlot. Pude crear diagramas simples de cuadros organizados en un círculo cortando y pegando los conjuntos de puntos de la salida en un archivo de datos y luego ejecutándolos

plot ''5.dat'' with boxxyerrorbars

Los .5 en el archivo sirven para dimensionar las cajas ... solución perezosa pero funcional. El .5 se aplica a ambos lados del centro, por lo que las cajas terminan siendo exactamente de tamaño 1.0.

Por desgracia, mi algoritmo no funciona . Hace que los radios sean demasiado grandes, por lo que las cajas están mucho más separadas de lo necesario. Incluso la reducción de la escala por un factor de 2 (podría haber sido un error usar 0.5 en algunos lugares) no ayudó.

Lo siento, me rindo. Tal vez mi enfoque pueda salvarse, pero no funciona como lo había hecho. :(

EDITAR

Odio rendirme. Estaba a punto de dejar mi PC cuando pensé en una manera de salvar mi algoritmo:

El algoritmo estaba ajustando la menor de las distancias X o Y para que fuera al menos 1. Es fácil demostrar que eso es simplemente tonto. Cuando tienes un montón de cajas, en los bordes este y oeste del círculo tienes cajas apiladas casi directamente una encima de la otra, con sus X muy cerca una de la otra, pero se salvan de tocar al tener una distancia suficiente entre Y ellos.

Entonces ... para hacer que esto funcione, debes escalar el máximo de dx y dy para que sea (para todos los casos) al menos el radio (¿o fue el doble del radio?).

El código corregido está aquí: http://ideone.com/EQ03g http://ideone.com/VRyyo

Probado nuevamente en GnuPlot, produce pequeños círculos hermosos de cajas donde a veces solo 1 o 2 cajas se tocan exactamente. ¡Problema resuelto! :)

(Estas imágenes son más anchas que altas porque GnuPlot no sabía que quería un diseño proporcional. Imagínese que todas las obras se comprimen en una forma cuadrada :))