计算半径R和尺寸D的球体内的整数点

我正在尝试编写一种有效的算法,该算法计算半径R和尺寸D的球体内的点数。球始终位于原点。假设我们有一个半径为5的尺寸为2(圆形)的球面。

我的策略是在第一个象限内生成所有可能的点,因此对于上面的示例,我们知道(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;

}

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

回答:

我在这里介绍了我的2D算法(带有一些源代码和一个难看但方便的插图)

它比MBo在四分之一之一的圆的原点和边缘之间的计数点快3.4倍。

您只是想像一个刻有正方形的正方形,并且只计算该圆圈内该正方形之外的东西的八分之一。

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;

}

以上是 计算半径R和尺寸D的球体内的整数点 的全部内容, 来源链接: utcz.com/qa/402875.html

回到顶部