快速解座標內/沿原點半徑爲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的時間，這是你可以做的，因爲它是點的數量最少。 您可以通過執行只有四分之一圈，並通過對稱得到其他的可能節省數計算，但我什至不知道它的速度更快，它肯定不再寫了。