计算半径R和尺寸D的球体内的整数点 [英] Counting integer points inside a sphere of radius R and dimension D

问题描述

我想写一个有效的算法来计算Radius R和Dimension D球体内的点数。球体总是在原点。假设我们有一个维度为2（圆）半径为5的球体。

我的策略是在第一个象限内生成所有可能的点，所以对于上面的例子， （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>点数; 
 std :: vector< int>点; 
 
 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; 
} 
  

在这种情况下我可以解决或改善什么？

解决方案

对于2D情况，这是 Gauss的一个可能的公式：

  N（r）= 1 + 4 * r + 4 * i = 1..r] {Floor（Sqrt（r ^ 2-i ^ 2））} 
  

（中心点+四个象限，轴上的点为4 * r，其他为象限区域）。

注意，没有已知的简单闭合数学表达式对于2D情况。

一般来说，你的想法与象限，八分圆等是正确的，但检查所有的点是太贵了。

可能会找到从1..D
整数正方形（（4）公式的延伸）构成从0到r ^ 2的所有正方形的方法的数量。 / p>

请注意，组合将有助于计算更快。例如，它足以找到到
的方法的数量使得X ^ 2从D自然正方形，并乘以2 ^ D（不同的符号组合）;找到从D-1自然正方形产生X ^ 2的方式的数目，并乘以D * 2 ^（D-1）（不同的符号组合+用于零加数的D个地方）等。

D = 2，R = 3的示例

 加数：0,1,4,9 
可能的总成分变体的数量
 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 
  

I am trying to write an efficient algorithm that counts the number of points inside a Sphere of Radius R and Dimension D. The sphere is always at the origin. Suppose we have a sphere of dimension 2 (circle) with radius 5.

My strategy is to generate all possible points within the first quadrant, so for the above example we know that (1,2) is in the circle, so must all + / - combinations of that point which is simply dimension squared. So for each point found in a single quadrant of an n-dimensional sphere we add 2 ^ dimension to the total count.

I'm not sure if there is a much more efficient solution to this problem but this is what I have so far in terms of implementation.

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

What can I fix or improve in this situation ?

解决方案

For 2D case this is Gauss's circle problem. One possible formula:

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

(central point + four quadrants, 4*r for points at the axis, others for in-quadrant region).

Note that there is no known simple closed math expression for 2D case.

In general your idea with quadrants, octants etc is right, but checking all the points is too expensive.

One might find the number of ways to compose all squares from 0 to r^2 from 1..D integer squares (extension of (4) formula).

Note that combinatorics would help to make calculation faster. For example, it is enough to find the number of ways to make X^2 from D natural squares, and multiply by 2^D (different sign combinations); find the number of ways to make X^2 from D-1 natural squares, and multiply by D*2^(D-1) (different sign combinations + D places for zero addend) etc

Example for 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

这篇关于计算半径R和尺寸D的球体内的整数点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！