Conteggio di punti interi all’interno di una sfera di raggio R e dimensione D

Sto provando a scrivere un algoritmo efficiente che conta il numero di punti all’interno di una sfera di raggio R e dimensione D. La sfera è sempre all’origine. Supponiamo di avere una sfera di dimensione 2 (cerchio) con raggio 5.

La mia strategia è quella di generare tutti i possibili punti all’interno del primo quadrante, quindi per l’esempio precedente sappiamo che (1,2) è nel cerchio, quindi devono tutte le combinazioni + / – di quel punto che è semplicemente la dimensione al quadrato. Quindi per ogni punto trovato in un singolo quadrante di una sfera n-dimensionale aggiungiamo 2 ^ dimensione al conteggio totale.

Non sono sicuro che esista una soluzione molto più efficiente a questo problema, ma questo è quanto ho finora in termini di implementazione.

int count_latex_points(const double radius, const int dimension) { int R = static_cast(radius); int count = 0; std::vector points; std::vector point; for(int i = 0; i <= R; i++) points.push_back(i); do { for(int i = 0; i < dimension - 1; i++) point.push_back(points.at(i)); if(isPointWithinSphere(point, radius)) count += std::pow(2,dimension); point.clear(); }while(std::next_permutation(points.begin(), points.end())); return count + 3; } 

Cosa posso aggiustare o migliorare in questa situazione?

Ho presentato il mio algoritmo per 2D qui (con qualche codice sorgente e un’illustrazione brutta ma a portata di mano): https://stackoverflow.com/a/42373448/5298879

È intorno a 3,4 volte più veloce dei punti di conteggio di MBo tra l’origine e il bordo del cerchio in uno dei quarti.

Immagina solo un quadrato inscritto e conta solo un ottavo di quello che c’è fuori da quel quadrato all’interno di quel cerchio.

 public static int gaussCircleProblem(int radius) { int allPoints=0; //holds the sum of points double y=0; //will hold the precise y coordinate of a point on the circle edge for a given x coordinate. long inscribedSquare=(long) Math.sqrt(radius*radius/2); //the length of the side of an inscribed square in the upper right quarter of the circle int x=(int)inscribedSquare; //will hold x coordinate - starts on the edge of the inscribed square while(x<=radius){ allPoints+=(long) y; //returns floor of y, which is initially 0 x++; //because we need to start behind the inscribed square and move outwards from there y=Math.sqrt(radius*radius-x*x); // Pythagorean equation - returns how many points there are vertically between the X axis and the edge of the circle for given x } allPoints*=8; //because we were counting points in the right half of the upper right corner of that circle, so we had just one-eightth allPoints+=(4*inscribedSquare*inscribedSquare); //how many points there are in the inscribed square allPoints+=(4*radius+1); //the loop and the inscribed square calculations did not touch the points on the axis and in the center return allPoints; } 

Per il caso 2D questo è il problema del cerchio di Gauss. Una ansible formula:

 N(r) = 1 + 4 * r + 4 * Sum[i=1..r]{Floor(Sqrt(r^2-i^2))} 

(punto centrale + quattro quadranti, 4 * r per i punti sull’asse, altri per la regione all’interno del quadrante).

Si noti che non esiste un’espressione matematica chiusa semplice nota per il caso 2D.

In generale la tua idea con quadranti, ottanti ecc. È giusta, ma controllare tutti i punti è troppo costoso.

Si potrebbe trovare il numero di modi per comporre tutti i quadrati da 0 a r ^ 2 da quadrati interi 1..D (estensione della formula (4)) .

Si noti che combinatorics aiuterebbe a rendere il calcolo più veloce. Ad esempio, è sufficiente trovare il numero di modi per rendere X ^ 2 dai quadrati naturali D e moltiplicare per 2 ^ D (combinazioni di segni diversi); trova il numero di modi per creare X ^ 2 dai quadrati naturali D-1 e moltiplica per D * 2 ^ (D-1) (combinazioni di segni diversi + punti D per zero addendi) ecc.

Esempio per D = 2, R = 3

 addends: 0,1,4,9 possible sum compositions number of variants 0 0+0 1 1 0+1,1+0 2*2=4 2 1+1 4 4 0+4,4+0 2*2=4 5 1+4,4+1 2*4=8 8 4+4 4 9 0+9,9+0 2*2=4 ------------------------------------- 29 

Un approccio simile a quello descritto da MBo , incluso il codice sorgente, può essere trovato su https://monsiterdex.wordpress.com/2013/04/05/integer-latex-in-n-dimensional-sphere-count-of-points -with-integer-coordinates-using-parallel-programming-part-i / .

L’approccio consiste nel trovare le partizioni del raggio, e quindi per ogni partizione nella sfera calcolare il numero di modi in cui può essere rappresentato nella sfera da entrambe le coordinate di permutazione e capovolgere i segni di coordinate diverse da zero.