algorithm - guia - qgis español

Cubra por completo un rectángulo con una cantidad mínima de círculos de radio fijo

Question

He tenido este problema por algunos años. Fue en un concurso de informática en mi ciudad hace un tiempo. No pude resolverlo, y mi maestro no pudo resolverlo. No he conocido a nadie que haya podido resolverlo. Nadie que conozca sabe la manera correcta de dar la respuesta, así que decidí publicarlo aquí:

Problema de Ze

Dado un rectángulo, X por Y, encuentre la cantidad mínima de círculos N con un radio fijo dado R, necesario para cubrir completamente cada parte del rectángulo.

He pensado en formas de resolverlo, pero no tengo nada definido. Si cada círculo define un rectángulo interno, entonces R^2 = Wi^2 + Hi^2 , donde Wi y Hi son el ancho y la altura del área práctica cubierta por cada círculo i . Al principio pensé que debería hacer Wi igual a Wj para cualquier i = j , lo mismo para H De esta forma, podría simplificar el problema haciendo que las relaciones ancho / alto sean iguales al rectángulo principal ( Wi/Hi = X/Y ). De esa forma, N=X/Wi . Pero esa solución seguramente es incorrecta en el caso de que X exceda en gran medida Y o viceversa.
La segunda idea fue que Wi = Hi para cualquier i dado. De esta forma, los cuadrados llenan el espacio de manera más eficiente. Sin embargo, si queda una tira muy angosta, es mucho más óptimo utilizar rectángulos para rellenarla, o mejor aún, usar rectángulos para la última fila antes de eso también.
Entonces me di cuenta de que ninguna de las ideas es la óptima, ya que siempre puedo encontrar mejores formas de hacerlo. Siempre será cercano al final, pero no final.

Editar
En algunos casos (rectángulo grande) unir hexágonos parece ser una mejor solución que unir cuadrados.

Editar más
Aquí hay una comparación de 2 métodos: trébol vs hexagonal. Hexagonal es, obviamente, mejor, para superficies grandes. Sin embargo, creo que cuando el rectángulo es lo suficientemente pequeño, el método rectangular puede ser más eficiente. Es una corazonada. Ahora, en la imagen, verá 14 círculos a la izquierda y 13 círculos a la derecha. Aunque la superficie difiere mucho más (doble) que un círculo. Es porque a la izquierda se superponen menos, por lo tanto, desperdician menos superficie.

Las preguntas aún permanecen:

1. ¿El patrón regular del hexágono es óptimo? O ciertos ajustes deben hacerse en partes del rectángulo principal.
2. ¿Hay razones para no usar formas regulares como "solución definitiva"?
3. ¿Esta pregunta tiene una respuesta? :)

Answer 1

Cuando los círculos se disponen como un trébol con cuatro hojas con un quinto círculo en el medio, un círculo cubrirá un área igual a R * 2 * R En esta disposición, la pregunta es: ¿cuántos círculos que cubren un área de R * 2 * R cubrirán un área de W * H ? , o N * R * 2 * R = W * H Entonces N = W * H / R * 2 * R

Answer 2

El hexágono es mejor que el diamante. Considere el área porcentual del círculo unitario cubierto por cada uno:

#!/usr/bin/env ruby

include Math

def diamond
  # The distance from the center to a corner is the radius.
  # On a unit circle, that is 1.
  radius = 1

  # The edge of the nested diamond is the hypotenuse of a
  # right triangle whose legs are both radii.
  edge = sqrt(radius ** 2 + radius ** 2)

  # The area of the diamond is the square of the edge
  edge ** 2
end

def hexagon
  # The hexagon is composed of 6 equilateral triangles.
  # Since the inner edges go from the center to a hexagon
  # corner, their length is the radius (1).
  radius = 1

  # The base and height of an equilateral triangle whose
  # edge is ''radius''.
  base = radius
  height = sin(PI / 3) * radius

  # The area of said triangle
  triangle_area = 0.5 * base * height

  # The area of the hexagon is 6 such triangles
  triangle_area * 6
end

def circle
  radius = 1
  PI * radius ** 2
end

puts "diamond == #{sprintf "%2.2f", (100 * diamond / circle)}%"
puts "hexagon == #{sprintf "%2.2f", (100 * hexagon / circle)}%"

Y

$ ./geometrons.rb 
diamond == 63.66%
hexagon == 82.70%

Además, los hexágonos regulares son polígonos de vértice más alto que forman una teselación regular del plano .

Answer 3

Este sitio ataca el problema desde un ángulo ligeramente diferente: dados n círculos de unidad, ¿cuál es el cuadrado más grande que pueden cubrir?

Como puede ver, a medida que cambia el número de círculos, también lo hace el patrón de cobertura.

Para su problema, creo que esto implica: diferentes dimensiones rectangulares y tamaños de círculo dictarán diferentes patrones de cobertura óptimos.

Answer 4

Para X e Y grande en comparación con R, un patrón hexagonal (panal) es casi óptimo. La distancia entre los centros de los círculos en la dirección X es sqrt(3)*R La distancia entre las filas en la dirección Y es 3*R/2 , por lo que necesita aproximadamente X*Y/R^2 * 2*/(3*sqrt(3)) círculos.

Si usa un patrón cuadrado, la distancia horizontal es mayor ( 2*R ), pero la distancia vertical es mucho más pequeña ( R ), por lo que necesitaría aproximadamente X*Y/R^2 * 1/2 círculos. Desde 2/(3*sqrt(3) < 1/2 , el patrón hexagonal es el mejor negocio.

Tenga en cuenta que esto es solo una aproximación. Por lo general, es posible agitar un poco el patrón regular para hacer que algo encaje donde el patrón estándar no lo haría. Esto es especialmente cierto si X e Y son pequeños en comparación con R.

En términos de sus preguntas específicas:

1. El patrón hexagonal es una cobertura óptima de todo el plano. Con X e Y finitos, creo que a menudo es posible obtener un mejor resultado. El ejemplo trivial es cuando la altura es menor que el radio. En ese caso, puede mover los círculos en una fila más separados hasta que la distancia entre los puntos de intersección de cada par de círculos sea igual a Y.

2. Tener un patrón regular impone restricciones adicionales a la solución, por lo que la solución óptima bajo esas restricciones puede no ser óptima con esas restricciones eliminadas. En general, los patrones algo irregulares pueden ser mejores (ver la página vinculada por mbeckish).

3. Los ejemplos en esa misma página son todas soluciones específicas. Las soluciones con más círculos se parecen un poco al patrón hexagonal. Aún así, no parece haber una solución cerrada.

Answer 5

Según mis cálculos, la respuesta correcta es:

D=2*R; X >= 2*D, Y >= 2*D,
N = ceil(X/D) + ceil(Y/D) + 2*ceil(X/D)*ceil(Y/D)

En caso particular si el resto para X / D e Y / D es igual a 0, entonces

N = (X + Y + X*Y/R)/D

Case 1: R = 1, X = 2, Y = 2, then  N = 4

Case 2: R = 1, X = 4, Y = 6, then  N = 17

Case 3: R = 1, X = 5, Y = 7, then  N = 31

Espero eso ayude.