Copertura di un'area arbitraria con cerchi di uguale raggio

Question

Come funziona un algoritmo che copre un'area arbitraria con cerchi di raggio uguale?

Il raggio del cerchio e le dimensioni e la forma dell'area sono date arbitrariamente. L'area dovrebbe essere coperta con il minor numero possibile di cerchi. I cerchi potrebbero sovrapporsi.

Esiste un algoritmo che gestirà questo?

Answer 1

Senza sapere di più sui propri vincoli, suggerirei di prendere una copertura regolare dell'aereo, con dischi corrispondenti agli esagoni regolari di una piastrellatura esagonale. Quindi mantieni tutti i dischi intersecanti la forma.

Answer 2

Spero di aver capito la tua domanda giusta ...

Si può dimostrare che esagonale Chiudere imballaggio (HCP) di sfere copre il volume massimo, utilizzando le sfere. Pertanto, suppongo che fare l'HCP con cerchi coprirà anche l'area massima usando cerchi. Tessellate la vostra area con triangoli e posizionate un cerchio con il centro su ciascun vertice del triangolo, con il raggio della metà della lunghezza del lato del triangolo. Vedi this per un'immagine dell'algoritmo di cui sto parlando.

Nota: questo è simile allo close packing of atoms in a unit cell.

MODIFICA: Il mio metodo precedente copre il più possibile l'area, senza sovrapposizioni. Se è consentita la sovrapposizione, quindi (credo che) il metodo seguente coprirebbe l'intera area con una sovrapposizione minima.

Come probabilmente sapete, ci sono solo 3 tassellazioni di spazio 2D con poligoni regolari - utilizzando quadrati, triangoli o esagoni. La strategia è quella di tessellare usando uno di questi poligoni e quindi circoscrivere un cerchio ad ogni poligono. Un esagono sprecherebbe l'area minima usando questo metodo.

Pertanto, dal raggio del cerchio dato, calcolare la dimensione degli esagoni necessari, tassellare l'area usando gli esagoni e quindi circoscrivere un cerchio su ciascun esagono.

NB:Eric Bainville suggerito un metodo simile.

-- Flaviu Cipcigan

Answer 3

so che questione può essere un po 'datato ma di recente ho avuto un problema simile con che copre un'area geografica con cerchi uguali con griglia esagonale e questo è come ho risolto:

1. mia i dati di input erano il raggio del cerchio dato in metri e le coordinate dei bordi dell'area
2. prima ho trovato il rettangolo di limiti che copre un'area data
3. quindi partendo dal basso a sinistra sposto il punto per distanza pari al doppio dell'altezza del triangolo usato per costruire l'esagono (il suo lato è lo stesso del raggio del mio cerchio) e rilevamento di 0 gradi usando le formule di Vincenty
4. per ogni punto che ho trovato, controllo se si interseca con la mia area di input, se la salvassi, altrimenti la salterò
5. quando sono arrivato a bordo faccio un altro controllo per assicurarmi che otterrò tutti i punti all'interno del sono
6. Sposto il punto per rilevamento di 60 gradi, controlla di nuovo, poi di 120 gradi, controlla di nuovo
7. torna al 3o passo ma ora sposto i punti per il rilevamento di 180 gradi
8. e il bordo ancora un altro controllo e poi come in 6a passo, ma prima di 120 gradi poi 60 gradi
9. proseguire fino ottenuto al bordo superiore del rettangolo

come in data immagine, naturalmente è possibile aumentare la precisione diminuendo raggio Cerchio

So che questa non è l'opzione migliore ma funziona abbastanza bene per me.

Spero sia abbastanza comprensibile e aiuterà chiunque.