riempiendo lo spazio con cerchi di dimensioni diverse

Question

Qui è il mio problema:

• Ho un sacco di cerchi che ho bisogno di visualizzare all'interno di una tela.
• C'è un numero arbitrario di cerchi, ognuno con un raggio predefinito.
• L'area sommata dei cerchi è sempre più piccola dell'area della tela.

Voglio posizionare i cerchi in modo che occupino lo spazio massimo disponibile all'interno della tela, senza toccarsi. Il mio obiettivo è ottenere un effetto visivamente piacevole in cui i cerchi appaiono ben distribuiti all'interno della tela. Non so se questo è davvero "spazio di riempimento", in quanto il mio obiettivo non è quello di ridurre al minimo la distanza tra gli elementi, ma piuttosto a massimizzare it.

Ecco un esempio di quello che sto cercando di realizzare:

La mia prima idea "forza bruta" è stato il seguente:

1. Per ogni cerchio: calcolare la distanza più breve tra il suo confine e il bordo di ogni cerchio; somma tutte queste distanze, chiama X.
2. Calcola la somma di tutte le X.
3. Cambia casualmente le distanze tra i cerchi.
4. Rifare 1-3 per un numero preimpostato di iterazioni e ottenere il valore massimo ottenuto al passaggio (2).

Tuttavia, questo non sembra elegante; Sono sicuro che c'è un modo migliore per farlo. Esiste un algoritmo esistente per ottenere tale layout? C'è qualche libreria esistente che potrei usare (JavaScript o Ruby) per raggiungere questo obiettivo?

Modifica

Ecco un Javascript version della risposta accettata, che utilizza Raffaello per disegnare i cerchi.

Answer 1

Vorrei provare a inserire la sfera dopo la sfera (prima la più grande). Ciascuno viene aggiunto nel più grande spazio disponibile, con qualche jitter casuale.

Un modo relativamente facile per trovare (più o meno) il più grande spazio disponibile, è immaginare una griglia di punti sulla tua vista e memorizzare per ogni punto della griglia (in un array 2D) la distanza più vicina a qualsiasi oggetto: bordo o sfera, a seconda di quale sia il più vicino. Questo array viene aggiornato ogni volta che viene aggiunta una nuova sfera.

Per aggiungere una nuova sfera, basta prendere il punto della griglia con la distanza massima e applicare un jitter casuale (in realtà sai quanto puoi fare jitter, perché sai la distanza dall'elemento più vicino). (Vorrei randomizzare non più di (d-r)/2 dove d è la distanza nell'array e r è il raggio della sfera da aggiungere.

L'aggiornamento di questo array dopo l'aggiunta di un altro cerchio non è una scienza missilistica: per ogni punto della griglia si calcola la distanza dalla sfera appena aggiunta e si sostituisce il valore memorizzato se questo era più grande.

È possibile che la griglia sia troppo grossolana e non è possibile aggiungere altri cerchi (quando l'array 2D non contiene distanze maggiori del raggio del cerchio da aggiungere). Quindi devi aumentare (ad esempio doppio) la risoluzione della griglia prima di continuare.

Ecco alcune risultato di questa implementazione (mi ci sono voluti circa 100 linee di codice)

• 100 cerchi di varie dimensioni

• 500 cerchi di varie dimensioni

• 100 Circoli della stessa dimensione

Ed ecco qualche codice di massima C++ (solo l'algoritmo, non aspettatevi questo per compilare)

// INITIALIZATION 

    // Dimension of canvas 
    float width = 768; 
    float height = 1004; 

    // The algorithm creates a grid on the canvas 
    float gridSize=10; 

    int gridColumns, gridRows; 
    float *dist; 

    void initDistances() 
    { 
     // Determine grid dimensions and allocate array 
     gridColumns = width/gridSize; 
     gridRows = height/gridSize; 

     // We store a 2D array as a 1D array: 
     dist = new float[ gridColumns * gridRows ]; 

     // Init dist array with shortest distances to the edges 
     float y = gridSize/2.0; 
     for (int row=0; row<gridRows; row++) 
     { 
     float distanceFromTop = y; 
     float distanceFromBottom = height-y; 
     for (int col=0; col<gridColumns; col++) 
     { 
      int i = row*gridColumns+col; 
      dist[i]=(distanceFromTop<distanceFromBottom?distanceFromTop:distanceFromBottom); 
     } 
     y+=gridSize; 
     } 
     float x = gridSize/2.0; 
     for (int col=0; col<gridColumns; col++) 
     { 
     float distanceFromLeft = x; 
     float distanceFromRight = width-x; 
     for (int row=0; row<gridRows; row++) 
     { 
      int i = row*gridColumns+col; 
      if (dist[i]>distanceFromLeft) dist[i] = distanceFromLeft; 
      if (dist[i]>distanceFromRight) dist[i] = distanceFromRight; 
     } 
     x+=gridSize; 
     } 
    } 

    void drawCircles() 
    { 
     for (int circle = 0; circle<getNrOfCircles(); circle++) 
     { 
     // We assume circles are sorted large to small! 
     float radius = getRadiusOfCircle(circle); 

     // Find gridpoint with largest distance from anything 
     int i=0; 
     int maxR = 0; 
     int maxC = 0; 
     float maxDist = dist[0]; 

     for (int r=0; r<gridRows; r++) 
      for (int c=0; c<gridColumns; c++) 
      { 
      if (maxDist<dist[i]) { 
       maxR= r; maxC= c; maxDist = dist[i]; 
      } 
      i++; 
      } 

     // Calculate position of grid point 
     float x = gridSize/2.0 + maxC*gridSize; 
     float y = gridSize/2.0 + maxR*gridSize; 

     // Apply some random Jitter 
     float offset = (maxDist-radius)/2.0; 
     x += (rand()/(float)RAND_MAX - 0.5) * 2 * offset; 
     y += (rand()/(float)RAND_MAX - 0.5) * 2 * offset; 


     drawCircle(x,y,radius); 


     // Update Distance array with new circle; 
     i=0; 
     float yy = gridSize/2.0; 
     for (int r=0; r<gridRows; r++) 
     { 
      float xx = gridSize/2.0; 
      for (int c=0; c<gridColumns; c++) 
      { 
      float d2 = (xx-x)*(xx-x)+(yy-y)*(yy-y); 

      // Naive implementation 
      // float d = sqrt(d2) - radius; 
      // if (dist[i]>d) dist[i] = d; 

      // Optimized implementation (no unnecessary sqrt) 
      float prev2 = dist[i]+radius; 
      prev2 *= prev2; 
      if (prev2 > d2) 
      { 
       float d = sqrt(d2) - radius; 
       if (dist[i]>d) dist[i] = d; 
      } 



      xx += gridSize; 
      i++; 
      } 
      yy += gridSize; 
     } 
     } 
    } 

Answer 2

Potrebbe essere utile qualche applicazione di force-directed layout.

Answer 3

Poiché il tuo obiettivo è solo "ottenere un effetto piacevole", non risolvere un problema di matematica, dovresti provare l'algoritmo più semplice che potrebbe funzionare prima e vedere se sembra buono. Non ci dovrebbe essere bisogno di usare la matematica molto complessa.

Capisco che si desidera che le sfere "riempiano" lo spazio disponibile, non lasciando grandi aree vuote mentre altre aree sono affollate. Vuoi anche che il layout appaia casuale, non allineato su una griglia o qualcosa del genere.

Il modo ovvio e semplice per raggiungere questo obiettivo è semplicemente posizionare le sfere una per una, in posizioni casuali. Se uno atterra sopra una sfera già posizionata, genera un'altra posizione casuale finché non ne trovi una dove si adatta.

Sembra che nell'immagine siano presenti circa 40 sfere. Le probabilità di 40 sfere tutte di atterrare nella stessa area dell'immagine, lasciando il resto dell'immagine vuoto, sono molto, molto piccole. Man mano che aumenta il numero di sfere, le probabilità di ottenere un layout molto sbilanciato si avvicinano allo zero.

Provatelo prima e verificate se soddisfa le vostre esigenze. Se non è abbastanza "uniforme", dovresti essere in grado di utilizzare una matematica molto semplice per forzare le posizioni scelte a caso in favore della scelta di aree vuote. Non dovrebbe essere necessario utilizzare algoritmi complessi.