半径Rと次元Dの球の内部の整数点を数える

Question

球の半径Rと次元Dの中の点の数を数える効率的なアルゴリズムを書こうとしています。球は常に原点です。

私の戦略は、第1象限内にすべての可能な点を生成することです。上の例では、（1,2）が円の中にあることがわかりますが、単に次元の二乗であるその点のすべての+/- の組み合わせでなければならない。したがって、n次元球の単一象限内にある各点に対して、総数に2次元を追加します。

この問題のはるかに効率的な解決策があるかどうかは分かりませんが、これはこれまでのところ実装の面でこれがあります。

int count_lattice_points(const double radius, const int dimension) { 
int R = static_cast<int>(radius); 

int count = 0; 

std::vector<int> points; 
std::vector<int> 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; 
} 

私はこの状況で何が改善できますか？ 2次元の場合について

Answer 1

私は（いくつかのソースコードと醜いが、便利なイラストで）ここでは、2Dのための私のアルゴリズムを提示： https://stackoverflow.com/a/42373448/5298879

をそれが原点と1の円のエッジとの間MBo'sカウントポイントよりも周りの3.4倍高速です四半期の

あなたはちょうど刻まれた正方形を想像して、その円の内側のその正方形の外側にあるもののわずか8分の1を数えます。

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; 
} 

Answer 2

これはGauss's circle problem.一つの可能​​な式である：

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

（中心点+ 4つの象限、軸でのポイントのために4 * rを、イン象限領域のためなど）。

2Dケースの単純な閉じた数式は知られていないことに注意してください。

通常、四分円、八角形などを使用したアイデアは正しいですが、すべての点をチェックするにはコストがかかりすぎます。

一つは1..D 整数乗（（4）式の拡張）から0からR^2にすべての正方形を構成するいくつかの方法を見つけるかもしれません。

コンビナトリアルは計算を高速化するのに役立つことに注意してください。例えば、 への道の数を見いだし、X^2をD個の自然数の正方形から作り、2^D（異なる符号の組み合わせ）で乗算すれば十分です。 D-1自然の四角からX^2を作る方法の数を求め、D * 2 ^（D-1）（ゼロの加数のために異なる符号の組み合わせ+ Dの場所）を掛け合わせるなど

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 

Answer 3

ソースコードを含むthat described by MBoと同様のアプローチ、 https://monsiterdex.wordpress.com/2013/04/05/integer-lattice-in-n-dimensional-sphere-count-of-points-with-integer-coordinates-using-parallel-programming-part-i/で見つけることができます。

球の中の各パーティションの半径を求めることは、置換座標とゼロ以外の座標の符号を反転させることによって、球で表現できる方法の数を計算することにあります。