快速解坐标内/沿原点半径为r为圆心

Question

想想看，你有0,0半径为r为中心的圆。

我想获得的所有整数关口可用的此圈子里面。这个问题很容易解决。

人们可能刚刚从x = -r to +r和y =-r to +r遍历一个正方形，看看if x * x + y * y <= r * r，如果是的话，点添加到您的结果。

然而，什么是做到这一点的最快方法？我觉得应该有一些类型的黑客，我们可以计算从(2r)^2到4/3 r^2

更具体地说，我有一种感觉，我们可以计算出内切正方形的长度，然后添加外其余的组件。我不确定如何做到这一点。数学有点密集。我不想发布代码，因为我想要一个通用的算法响应，但如果有偏好，他可能会陈述最终的基准，它将用于使用JVM语言。

任何帮助？

注：这是类似高斯的圈子的问题，但不是计数点的数量，我想知道的点。

for x in [-floor(r), floor(r)] 
    y_max = floor(sqrt(r^2 - x^2)) # Pythagora's theorem 
    for y in [-y_max, y_max] 
     # (x, y) is good ! 

：

Answer 1

可以直接通过计算最大y获得的值那样的x的每个值（第二圆上的点的在垂直的（X，0）坐标）我认为你可以做得更好（也许你可以更快地计算y_max，但这不会是一个很大的胜利），因为无论如何，你在结果中有这些点。

编辑：

这是PI * R^2的时间，这是你可以做的，因为它是点的数量最少。 您可以通过执行只有四分之一圈，并通过对称得到其他的可能节省数计算，但我什至不知道它的速度更快，它肯定不再写了。