imballaggio cerchi irregolari sulla superficie di una sfera

Question

sto usando Three.js per creare punti su una sfera, simile al

Il mio set di dati periodic table of elements example è un cerchi di dimensioni irregolari, e auguro a loro distribuire uniformemente attorno alla superficie di una sfera. Dopo numerose ore di ricerche sul web, mi rendo conto che è molto più difficile di quanto possa sembrare.

Ecco alcuni esempi di questa idea in azione:

vimeo

pic

circlePack java applet

Qualcuno può aiutarmi a puntare nella direzione per la ricerca di un algoritmo che mi permetterà di fare Questo? Il rapporto di imballaggio non deve essere molto alto e sarebbe idealmente una cosa facile e veloce da calcolare in javascript per il rendering in THREE.js (sistema cartesiano o di coordinate). L'efficienza è la chiave qui.

Modifica: i raggi del cerchio possono variare notevolmente. Ecco un esempio utilizzando il codice tabella periodico:

Answer 1

Ecco qualcosa su cui puoi costruire forse. Distribuirà in modo casuale le sfere lungo una sfera. In seguito continueremo a ripetere questo punto di partenza per ottenere una distribuzione uniforme.

//random point on sphere of radius R 
var sphereCenters = [] 
var numSpheres = 100; 
for(var i = 0; i < numSpheres; i++) { 
    var R = 1.0; 
    var vec = new THREE.Vector3(Math.random(), Math.random(), Math.random()).normalize(); 
    var sphereCenter = new THREE.Vector3().copy(vec).multiplyScalar(R); 
    sphereCenter.radius = Math.random() * 5; // RANDOM SPHERE SIZE, plug in your sizes here 
    sphereCenters.push(sphereCenter); 
    //Create a THREE.js sphere at sphereCenter 
    ... 

} 

Quindi eseguire il codice qui sotto un paio di volte per imballare le sfere in modo efficiente:

for(var i = 0; i < sphereCenters.length; i++) { 
    for(var j = 0; j < sphereCenters.length; j++) { 
     if(i === j) continue; 
     //calculate the distance between sphereCenters[i] and sphereCenters[j] 
     var dist = new THREE.Vector3().copy(sphereCenters[i]).sub(sphereCenters[j]); 
     if(dist.length() < sphereSize) { 
      //move the center of this sphere to to compensate 
      //how far do we have to move? 
      var mDist = sphereSize - dist.length(); 
      //perturb the sphere in direction of dist magnitude mDist 
      var mVec = new THREE.Vector3().copy(dist).normalize(); 
      mVec.multiplyScalar(mDist); 
      //offset the actual sphere 
      sphereCenters[i].add(mVec).normalize().multiplyScalar(R); 

     } 
    } 
} 

esecuzione la seconda sezione di un certo numero di volte si "convergono" sulla soluzione che stai cercando. Devi scegliere quante volte dovrebbe essere eseguito per trovare il miglior compromesso tra velocità e precisione.

Aggiornamento per la precisione

Answer 2

È possibile utilizzare lo stesso codice della tabella periodica degli elementi. I rettangoli non si toccano, quindi è possibile ottenere lo stesso effetto con le cerchie, praticamente usando lo stesso codice.

ecco il codice che hanno:

  var vector = new THREE.Vector3(); 

      for (var i = 0, l = objects.length; i < l; i ++) { 

       var phi = Math.acos(-1 + (2 * i)/l); 
       var theta = Math.sqrt(l * Math.PI) * phi; 

       var object = new THREE.Object3D(); 

       object.position.x = 800 * Math.cos(theta) * Math.sin(phi); 
       object.position.y = 800 * Math.sin(theta) * Math.sin(phi); 
       object.position.z = 800 * Math.cos(phi); 

       vector.copy(object.position).multiplyScalar(2); 

       object.lookAt(vector); 

       targets.sphere.push(object); 

      } 

Answer 3

Ecco un metodo per provare: una ricerca iterativa utilizzando una forza repulsiva simulato.

Algoritmo

Prima inizializzare i dati impostati disponendo i cerchi attraverso la superficie in qualsiasi tipo di algoritmo. Questo è solo per l'inizializzazione, quindi non deve essere grande. Il codice periodico della tabella funzionerà bene. Inoltre, assegna a ogni cerchio una "massa" usando il suo raggio come valore di massa.

Ora avviare l'iterazione per convergere su una soluzione. Per ogni passaggio attraverso il ciclo principale, effettuare le seguenti operazioni:

1. Calcolare le forze repulsive per ciascun cerchio. Modella la tua forza repulsiva dopo la formula per la forza gravitazionale, con due regolazioni: (a) gli oggetti dovrebbero essere spinti di distanza l'uno dall'altro, non attratti l'uno verso l'altro, e (b) sarà necessario modificare la "forza costante" valore per adattarsi alla scala del tuo modello. A seconda della tua abilità matematica potresti essere in grado di calcolare un buon valore costante durante la pianificazione; altri saggi sperimentano un po 'all'inizio e troverai un buon valore.

2. Dopo aver calcolato le forze totali su ciascun cerchio (cercare il problema con il n-corpo se non si è sicuri di come farlo), spostare ciascun cerchio lungo il vettore della sua forza calcolata totale, utilizzando la lunghezza di il vettore come distanza da spostare. Questo è dove potresti scoprire che devi modificare il valore della forza costante. All'inizio vorrai movimenti con lunghezze inferiori al 5% del raggio della sfera.

3. I movimenti del passaggio 2 hanno spinto i cerchi fuori dalla superficie della sfera (poiché si respingono a vicenda). Ora sposta ciascun cerchio verso la superficie della sfera, nella direzione verso il centro della sfera.

4. Per ciascun cerchio, calcolare la distanza dalla vecchia posizione del cerchio alla sua nuova posizione. La maggiore distanza spostata è la lunghezza del movimento per questa iterazione nel ciclo principale.

Continua a scorrere per un istante attraverso il loop principale. Nel tempo la lunghezza del movimento dovrebbe diventare sempre più piccola man mano che le posizioni relative dei cerchi si stabilizzano in una disposizione che soddisfa i tuoi criteri. Esci dal ciclo quando la legth del movimento scende sotto un valore molto piccolo.

Ottimizzare

si potrebbe scoprire che è necessario modificare il calcolo forza per ottenere l'algoritmo di convergere su una soluzione. Il modo in cui modifichi dipende dal tipo di risultato che stai cercando. Inizia a modificare la forza costante. Se ciò non funziona, potrebbe essere necessario modificare i valori di massa in alto o in basso. O forse cambia l'esponente del raggio nel calcolo della forza. Per esempio, invece di questo:

f = (k * m[i] * m[j])/(r * r); 

si potrebbe provare questo:

f = (k * m[i] * m[j])/pow(r, p); 

Quindi è possibile sperimentare con diversi valori di p.

È anche possibile sperimentare diversi algoritmi per la distribuzione iniziale.

La quantità di tentativi ed errori dipende dagli obiettivi di progettazione.