Cubriendo un área arbitraria con círculos de igual radio

Question

¿Cómo funcionaría un algoritmo que cubre un área arbitraria con círculos de igual radio?

El radio del círculo y el tamaño y la forma del área se dan arbitrariamente. El área debe cubrirse con el menor número de círculos posible. Los círculos pueden superponerse.

¿Hay algún algoritmo que pueda manejar esto?

Answer 1

Sin saber más acerca de sus limitaciones, le sugiero que tome una cobertura regular del avión, con los discos correspondientes a los hexágonos regulares de un mosaico hexagonal. Luego mantenga todos los discos intersectando la forma.

Answer 2

esperanza he entendido su pregunta correcta ...

Se puede demostrar que hexagonal de embalaje (HCP) de esferas cubre el volumen máximo, utilizando esferas. Por lo tanto, asumo que hacer HCP con círculos también cubrirá el área máxima usando círculos. Tesee su área con triángulos y coloque un círculo con el centro en cada vértice del triángulo, con el radio la mitad de la longitud del lado del triángulo. Consulte this para obtener una imagen del algoritmo del que estoy hablando.

Nota: Esto es similar al close packing of atoms in a unit cell.

EDIT: Mi método anterior abarca la mayor área posible, sin superposición. Si se permite la superposición, entonces (creo que) el siguiente método cubriría toda el área con una mínima superposición.

Como probablemente sepa, solo hay 3 teselaciones de espacio 2D con polígonos regulares, con cuadrados, triángulos o hexágonos. La estrategia es teselar usando uno de estos polígonos y luego circunscribir un círculo a cada polígono. Un hexágono desperdiciaría el área mínima con este método.

Por lo tanto, a partir del radio del círculo dado, calcule el tamaño de los hexágonos necesarios, tesele el área usando los hexágonos y luego circunscriba un círculo en cada hexágono.

NB:Eric Bainville sugirió un método similar.

-- Flaviu Cipcigan

Answer 3

Sé que la pregunta puede ser un poco anticuado, pero poco recibí un problema similar con que cubre la zona geográfica con círculos iguales usando rejilla hexagonal y así es como lo resolví:

1. mi los datos de entrada fueron el radio del círculo dado en metros y las coordenadas de los bordes del área
2. primero encontré el rectángulo de límites que cubre el área dada
3. comenzando desde la parte inferior izquierda muevo el punto por distancia igual al doble de la altura del triángulo utilizado para construir el hexágono (su lado es el mismo del radio de mi círculo) y teniendo 0 grados usando las fórmulas de Vincenty
4. por cada punto que encontré, verifico si se cruza con mi área de entrada, si la guardo, de otra manera la omito
5. cuando llegué al borde realizo una comprobación más para asegurar que obtendré todos los puntos dentro de
6. muevo el punto por 60 grados, compruébalo, luego en 120 grados, verifique de nuevo
7. regrese al 3er paso pero ahora muevo los puntos por rumbo de 180 grados
8. y el borde una vez más Y entonces, como en sexto paso, pero primero 120 grados luego de 60 grados
9. continuará hasta que llegó hasta el borde superior del rectángulo

como en la imagen que se da, por supuesto, puede aumentar la precisión al disminuir el radio de círculo

Sé que esta no es la mejor opción, pero funciona bastante bien para mí.

Espero que sea bastante comprensible y ayude a cualquiera.